問題タブ [automata-theory]

Σ={ a, b, c, d } L={ x ∈ Σ* | x は "bab" で始まったり終わったりしていません }

受け入れられるべき例:

• アババ
• アバブク
• ババブ
• ババ
• ab
• バ
• ああああ
• ɛ

拒否する必要がある例:

• バブ
• 馬場
• バブク
• キャバブ
• アバブ

私は何度か試しましたが、これまでのところ：

私のdfaの主な問題は、「bbab」を受け入れることです

ありがとうございました。

A が有限であるか、自然数に 1 対 1 でマッピングされている場合、セット A は可算であることがわかっています。

ALPH が任意の有限アルファベットであるとします。

私の推論を要約します。

a) ALPH 上の任意の各言語はカウント可能です。（これは本当だと思います）

b) ALPH からのすべての言語のセットは可算です (これは誤りだと思います)。

c) ALPH 上の任意の言語ごとに、生成形式文法があります。(これは嘘だと思います)

d) 形式文法によって生成できる ALPH 上の任意の各言語は、再帰的です。（これは本当だと思います）

誰かが私を助けてくれますか？

オートマトンコースについてのメモを読みました。この注記を参照してください。以下はすべて同じです。しかし、L(g) は NFA や正規表現と等しくないと思います。誰でもこの図の言語を定義するのを手伝ってくれます (nfa、正規表現、文法):

したがって、上記の例では、物事はかなり簡単です.null可能なシンボルを見つけ、εを削除し、空の文字列なしで仕事を成し遂げることができる新しいプロダクションを構築すると、これが得られます..

そして、私はこの例に出くわしました

A は B を生成し、B は明らかに空の文字列を生成できます。Aがnullableであることを意味するのはSであり、null可能な端末を直接生成しない場合、端末を無効にすることは可能ですか?

だから私は、プッシュダウン オートマトンと文脈自由言語に関するテストの勉強をしていて、この 1 つの構造に固執しています。

以下で説明する 1 つの部分を除いて、このオートマトンのすべての部分が完全に機能しています。

認識する必要がある言語は次のとおりです。{ x#y#z#w | x, y, z, w in {0, 1}+ with x ≠ w and y ≠ z }.

したがって、私が抱えている問題は、Xi と Wi を比較することです。これは、オートマトンが W を処理する時点では Wi の要素がわからないためです。これは、私が設計した方法です。

X の内容を格納すると、各要素をポップオフして W の要素と比較するときに、逆の順序でポップオフするため、000111 と 111000 が同じ文字列であると見なされ、PDA は拒否する必要がありますが拒否されます。明確に受け入れます (それらは異なる文字列です)。これは一例にすぎません。これにより、他の入力が正しく分析されなくなります。

X の内容を逆の順序でスタックにプッシュする方法があれば、それらは元の形式でポップオフされるため、文字列の内容を正しく比較できます。

普通にプッシュした後にスタックの内容を逆にする方法があれば、これも解決策にたどり着くことができます。

どんな助けでも大歓迎です。ありがとう。

PDA を使用して CFG またはタイプ 2 グラマーの遷移を定義する際に、Zo で示される初期スタック シンボルが必要です。私の疑問は、最終的にスタックをまったく空にするので、なぜそれが必要なのかということです....??

私は閉じた和集合操作定理の下で正規語を学んでいます。Q,F,q _oを取得しましたが、デルタ δ を取得するのに混乱しています。特にデルタセクションを例で説明してください。

文脈自由文法を最初にチョムスキー標準形に変換して、それをグライバッハ標準形に変換する必要がありますか?