正規表現です。レギュラーまたは不規則？

私はちょうどこれらの表現と不規則であるか正規であるかの2番目のopionionを取得したいと思います。正規表現です。レギュラーまたは不規則？

{0^n 1^m | n >= m >=0} REGULAR

{0^n 1^m | n,m >=0}* REGULAR

{0^n 0^n | n>=0} IRREGULAR

誰もこれが真実であることを確認することができますか？

出典

2011-10-24 Anonymous

あなたは宿題としてこれをタグ付けする必要があるようです。 – mah

ああ申し訳ありませんが新しい私は、hwタグがあった知っていません。これを確認することができますか、またはサイトの仕組みに無知であることを私を批判するためだけにここにありますか？ –

あなたは決して使用されないMについて話します。 –

{0^n 1^m | n >= m >=0} n> = mを保証するためにnが何であったかをFSMが追跡できないため、FSMは式を表すことができません。

{0^n 1^m | n,m >=0}* - FSMはこれを表すように見えますが、問題があります。第1の問題とは異なり、nとmは互いに無関係であるため、FSM作成の問題はありません。問題は、マシンを複数回通過する場合、nとmが同じでなければならないことです。繰り返しますが、記憶がないので、これは不可能です。

{0^n 0^n | n>=0} - これはFSMでも簡単です。それは2番目の問題のFSMのように見えます。 REは(00)*

出典

2011-10-24 11:10:08 mah

私はあなたが '{0^n 1^m | n、m> = 0} * 'として、NFAを構築することができ、' 1^m'に対してNFAを構築することができる。それゆえ、連鎖性はあるものの、 '0^n 1^m'のためのNFAを構築することができるので、連鎖反応にkleene closureを適用するのは簡単です。これをRE '（0 | 1）*' –

@Bodylossと表現することができるようです。最後にクレーネの星でなかったら、正しいでしょう。問題は、2番目のFA（1^m）から最初のループにループするとき、nとmの値は、マシンを最初に通過したときの値と同じでなければならず、メモリがなければ、isn可能です。 – mah

ああ、 'n、m> = 0'と言っても、マシンを通過すると' n = m'という意味になりますか？あたかもそうでないかのように、あなたはA = {0^n 1^m | n、m> = 0} 'Thompsonsの構築を使用していますか？ –

正規表現です。レギュラーまたは不規則？

答えて

関連する問題