プロが教えるわが家の防犯対策術!

{xx^r | x∈T^*}
(x^rはxと文字列が逆さま。つまりxx^rは回文)
が正規言語でないことを証明せよという問題で、他の問題を参考にして自分ではこう考えました。


Lが正規言語と仮定し、状態数nについて、

z = a^nb^nb^na^n を考える。

|z|>n であり、

z = uvw ,|uv|≦n ,|v|≧1 となるu,v,wが存在して

任意のiについて、

uv^iw ∈ L

今i=0とおく。v=a^k (k≧1)であるから、

uw中のaの数は n + n-k
uw中のbの数は n + n

よってa^nb^nb^na^nはaとbの数が等しくないといけないから uw ∈ L に矛盾。

よってLは正規言語ではない。

これはあってますか?回答がないため、確認する手段がなく困っています。
もし違っていればその箇所をご指摘ください。

A 回答 (2件)

えーと、それでは、「受理する」と「決定性」とは?


やっぱり答えられないような気がしてきました・・・
    • good
    • 1

数学基礎論をやっている人は世の中それほど多いとは思えないので、


少なくとも正規言語、状態数ぐらいは定義してもらわないと
みなさん回答できないと思います。

もちろん、定義してもらっても分からないかも知れません。

この回答への補足

ここでいう正規言語とは

Lは正規言語である=
Lを受理する有限決定性オートマトンもしくは、非決定性オートマトンを設計することが出来る

です。なので状態数はオートマトンの状態数のことです

補足日時:2003/11/25 14:19
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!