次の問題に近づくのに問題があります。
次の言語の文脈自由文法を教えてください.
{x#y | x,y in {0,1}* and |x| != |y|}
この質問にアプローチする最良の方法は何ですか? 現時点では、直感を使ってこのような質問を解決していますが、役立つテクニックはありますか? つまり、この言語の PDA がどのようになるかを考えて、そこから文法を導出できますか? 文法 A と B を使用して文法 G = A と B を見つける方法はありますか?
これを解決する方法を見つけるのに苦労しているので、どんな助けでも大歓迎です。
ありがとう。
直感を使うことは貴重なテクニックです。そのような問題を解決すればするほど、直感が研ぎ澄まされ、より簡単になります。
言語の記述を CFG に変換するための正式な手法はありません (もちろん、記述が一連のプロダクション ルールのように CFG にマッピングされるものでない限り)。一般に、言語が文脈自由であるかどうかを決定することはできません (ただし、CFG は多くの制約に準拠する必要があるため、カウント引数を使用して半機械的にさえ、言語が CFG ではないことを証明することはしばしば可能です)。 2 つの文脈自由言語の共通部分が文脈自由であるとは限りません。そのため、2 つの文脈自由言語を取り、それらの結合に対して CFG を生成できる手順はありません。
ただし、2 つの文脈自由言語の結合は文脈自由であり、CFG は 2 つの言語の CFG から機械的に生成できます。したがって、問題をバラバラに分解する可能性があります。
この特定の問題の場合、私は単純なヒューリスティックを提案します。これは、正式な言語の授業で受ける類の質問でよく機能します。答えがわかっている単純な問題に基づいて問題を作成してみてください。
上記のように、2 つの CFL の和集合は文脈自由です。次のように定義される連結も同様です。
L1・L2 = { xy | _ x ∈ L 1 ∧ y ∈ L 2 }
ここに 2 つのアプローチがあります。どちらも同様の言語を構築できることに基づいています。× | = | y |。| の任意の文字列 × | ≠ | y | 右側または左側に文字を追加する必要があります。好みに応じて、これらの余分な文字を中央 (セパレーターの片側または反対側) または端の 1 つに追加できます。これらのアプローチはどちらもユニオンの使用を伴います。1 つは連結で、もう 1 つは埋め込みです。
幸運を。