プッシュダウン オートマトン (PDA) を生成して、10 個の部分文字列と同じ数の 01 部分文字列が存在し、11 個の部分文字列と同じ数の 00 部分文字列が存在することを確認するように求められました。
問題は次のとおりです。
L1 ⊆ {0, 1}* を、10 個の部分文字列と同じ数の 01 部分文字列と、11 個の部分文字列と同じ数の 00 部分文字列を持つ文字列の言語とする。(注: 000 には 2 つの 00 部分文字列があります) 言語 L1 を認識するプッシュダウン オートマトンを生成します。
これまでのところ、後で PDA に変換できる CFG の作成を試みました。両方の条件が満たされていることを確認するための CFG を生成できないように見えるので、運が悪いです。
次のような文法規則の多くの CFG バリエーションを試しました。
S -> 00S11S | 11S00S | 01S10S | 10S01S | 010S | 101S | 00110S | ϵ
また、01、10、00、11 の各出現をそれぞれ A、B、C、D として PDA スタックに格納しようとしました。私は単純に、A を B に、C を D に一致させてポップできると考えました。残りの文字は、条件を満たさないことを警告してくれます。
誰かが私を正しい方向に導くためのヒントを提供できますか?