No.2ベストアンサー
- 回答日時:
> という場合がありえますが
----------** 最後のa..ab、
を忘れていました。どっちにしても結論はかわりませんが、訂正します。
あと、ついでなので1つアドバイス的なことを。
正規表現の能力の限界は、直観的には、DFAが有限の状態しか持たないということに起因します。
例えば、(^i )^i(=同じ数の対応する括弧)が正規表現で表せないことはご存知ですよね。
これは、「(^i が入力された時点で、今までに何個の( が入力されたかを覚えておく必要があるが、それは有限の状態では不可能だから」と理解することができます。
こう理解しておくと、証明するまでもなく、{ww: w∈{a, b}*} は正規言語ではないということが予想できるかと思います。
この回答へのお礼
お礼日時:2004/11/20 04:15
さっき試験が返ってきました。
当然×でした、とほほ。
(^i )^iは今まで見たことありませんでした。
試験前に知っておけばよかったです。
ありがとうございました。
No.1
- 回答日時:
残念ながら(?)、{ww: w∈{a, b}*} も Non-regular です。
これは、{ww^R: w∈{a, b}*}が Non-regular であることの証明とほぼ同じように示すことが出来ます。
あまり厳密な証明ではないですが、簡単に説明すると・・・
{ww: w∈{a, b}*}を受理するDFAが存在したとすると、
このDFAは、(a^n)b(a^n)b という記号列を受理するはずです(a^nはaのn個の並び)。
DFAの状態数は有限なので、nがある一定以上大きくなると記号列長が状態数を超えます。
そのような記号列を受理するためには、必ずDFA中の同じ状態を2度通る必要があります。つまり、
Sk → ... → Sk
という遷移のループがDFAに必ず存在します。
(a^n)b(a^n)bを受理した際、このループで処理した記号列は、
a...aba...ab のうち、
-***-------- このあたりか(前半のa)、
----***----- このあたりか(a...aba...a、または前後のaを含まない場合)、
-------***-- このあたりか(後半のa)、
-----------* 最後のbだけ、
という場合がありえますが(多分表示がずれますが、だいたいわかりますよね)、
このうちのどれであったとしても、このようなループが存在すると、このDFAは{ww: w∈{a, b}*} に含まれない記号列も受理できることになってしまいます。
これは矛盾であり、{ww: w∈{a, b}*}を受理するDFAは存在せず、つまり{ww: w∈{a, b}*}は正規言語ではない、ということになります。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 債券・証券 米国の高金利にあやかる方法は何がベスト? 2 2022/09/24 20:30
- その他(言語学・言語) 英語の翻訳をご指導、教えてくださる方いらっしゃいませんか? 2 2023/05/24 12:15
- 英語 カンマの意味 2 2022/10/25 08:16
- 英語 この英文は分詞構文ですか? 4 2022/08/31 13:46
- 飲み物・水・お茶 UCCゴールドスペシャルは、インスタントコーヒーですか。 レギュラーコーヒーですか。 https:/ 1 2022/03/23 18:40
- 英語 Language is unique to human beings. beingsってどういう意味 2 2022/04/14 21:53
- 格安スマホ・SIMフリースマホ スマホ 3 2022/07/07 17:22
- 英語 英語に詳しい方、助けて下さい。 He found an ideal environment in w 5 2023/03/13 21:34
- その他(プログラミング・Web制作) vscodeエラー 1 2022/05/01 21:01
- 訴訟・裁判 誹謗中傷 訴えられるか 同定可能性 1 2023/02/08 00:38
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
プログラミングについて。 1つ...
-
エクセルの当番表を作っていま...
-
ネットワークループとルーティ...
-
どなたかこのプログラミングを...
-
VBA for i=1 to lastrow
-
画面を強制的に再描画させる方法
-
【VBA】指定の範囲から特定の文...
-
while(*s++=*t++)の判定は?
-
イベントの発生を待つ
-
Escキーを押すと、中断する時と...
-
GIFアニメをループさせたくない
-
UWSCの終了の仕方
-
「VC++6」ウィンドウの再描画
-
Java 南京錠
-
EXCEL VBA(初心者)印刷ルー...
-
磁気ループ装置の仕組みと作り方
-
VBA Dir関数でファイルをループ...
-
重複データをテーブルに表示し...
-
一巡伝達関数と開ループ伝達関数
-
CreateJS(TweenJS)での連続した...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
画面を強制的に再描画させる方法
-
VBAで3秒だけ時間を止めたい
-
VBAでの一時停止と再開の方法
-
どなたかこのプログラミングを...
-
Escキーを押すと、中断する時と...
-
UWSCの終了の仕方
-
エクセルの当番表を作っていま...
-
VBA for i=1 to lastrow
-
「偶数・奇数の和」のフローチ...
-
アクティブセルから、A列最終行...
-
DoEventsが必要な理由について
-
vb.netからエクセル関数書き込み
-
GIFアニメをループさせたくない
-
DOSコマンドのループ内のTIMEコ...
-
範囲指定したセルを1つずつ飛...
-
流れ図(フローチャート)が分か...
-
乱数の桁数指定、または範囲指定。
-
テキストボックスの名前に変数...
-
CSVファイルの特定の行だけを読...
-
vb.netです。2次元配列の要素を...
おすすめ情報