{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件)
- 最新から表示
- 回答順に表示
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 日本語 意味とは何か? どこにあるのか?(Ⅱ) 4 2022/04/21 13:35
- 数学 テキストに打ち込むのが大変なので手書きの写真で失礼します。見づらかったら言ってください(T_T) < 5 2022/04/18 11:06
- カスタマイズ(車) 走り屋、峠、ドリ車ベースとしてなぜ歴代ロードスターは不人気なのか? 7 2022/09/20 07:35
- 法学 間違った回答のベストアンサーの問題 19 2023/05/17 11:58
- 高校 読解力をつけたい 2 2023/06/10 15:11
- 高校 テスト勉強について 中間テストの結果がかえってきたのですがあまりよくありませんでした。 現代の国語と 2 2023/06/05 00:46
- 大学受験 新高3男子です。 共通テスト国語過去問研究と書かれている赤本を今日から始めました。 まずは2015年 4 2022/03/28 10:39
- その他(教育・科学・学問) 英文校正についての質問 1 2022/06/14 14:58
- 英語 ”be”<動詞>と<助動詞>混同の誤り ― 形式主義文法論の混迷 12 2022/05/17 11:09
- 哲学 《言語記号の恣意性》なる仮説を問い直し 《無主体》を説く構造主義を批判します 2 2023/05/10 04:37
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
皆さん定義を教えてください 「...
-
べき乗
-
えっ!「来週」の使い方…
-
ACCESS VBAでインポート定義の場所
-
無限から無限を引いたら何にな...
-
1未満と1以下の違い
-
(-1) ^2πってなんで1じゃないん...
-
変数の宣言の名称を教えてくだ...
-
質問の定義が分からないので確...
-
なぜ、直角三角形ではないのにs...
-
論理に於る=と⇔の違い
-
\\mathrmと\\rmの違いについて...
-
ヘシアンが0の場合どうやって極...
-
e<3の証明を教えてください。
-
「互いに素」の定義…「1と2は互...
-
「logx^2=2logx」が間違って...
-
数学の解答を見て、ああなるほ...
-
√ ルート 定義
-
texのchapterの改ページについて
-
日本語 ことば ひとまわり ふた...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
べき乗
-
皆さん定義を教えてください 「...
-
「互いに素」の定義…「1と2は互...
-
無限から無限を引いたら何にな...
-
1未満と1以下の違い
-
0を0 乗すると答えは1ですか 考...
-
変数の宣言の名称を教えてくだ...
-
「logx^2=2logx」が間違って...
-
ACCESS IIF関数 複数条件の設...
-
ACCESS VBAでインポート定義の場所
-
日本語 ことば ひとまわり ふた...
-
なぜ、直角三角形ではないのにs...
-
ヘシアンが0の場合どうやって極...
-
マイナス7は素数ですか?
-
複雑な家庭とは
-
数字の1とは何なのか?
-
最大元と極大元の定義の違いが...
-
eの0乗は1ってどういう原理です...
-
中年の定義を教えてくださいよ...
-
texのchapterの改ページについて
おすすめ情報