5

この言語が規則的かどうかを確認するタスクが与えられました。

L = {w∈{a,b,c}* | where the number of a is less than the number of b+c.}

これに対する正規表現も、決定論的 (またはそうでない) 有限状態オートマトンも見つかりません。一方、ポンピングの補題定理で逆を証明する方法は見つかりませんでした。

何か案は？

4

1 に答える 1

3

免責事項

ポンピング補題を使用した正式な証明が上記に投稿されていることを知っています。ただし、正式な解決策に進む前に、問題についてある程度の直感を持っておくと通常は役立つと思うので、完全に非公式な説明を行います。

一般的な直感

一般に、言語がある種のカウントに依存している場合、それはおそらく規則的ではないというベルを鳴らす必要があります。その理由は、カウントが任意に大きくなる可能性があるためです。これはあなたの例で具体的に見ることができます。

なぜ定期的ではないのですか？

あなたの言語のDFSを作成しようとしていると想像してみてください。気になるのは、との数との数の合計の違いです（aこれを呼び出します）。DFSでは、すべての情報が状態自体でキャプチャされます。例として、10回連続で読み取った後の状態と100回連続で読み取った後の状態を考えてみます。これらの2つの状態は異なっている必要があります。ここで、この引数を任意の数（または同等に任意の）に拡張すると、無限の数の状態が必要である、つまり言語が規則的ではないと結論付けることができます。bcD_abcaaaD_abc

ボーナス：なぜ文脈自由なのですか？

ここで、プッシュダウンオートマトンの使用について考えてみましょう。PDAを使用すると、（無限の）スタックを使用して、（無限の）カウントの難しさを把握できます。あなたの例では、次のように行うことができます。

  • スタックが空の場合（つまりD_abc = 0）、遭遇したシンボルをスタックにプッシュします（つまり、aが来るD_abc <- 1場合、bまたはcが来る場合D_abc <- -1）。

  • スタックの一番上の要素がa（つまりD_abc> 0）の場合、aスタックにプッシュします（つまりD_abc <- D_abc + 1、そうでない場合は、スタックから一番上をポップしaます（つまりD_abc <- D_abc - 1）。

  • 同様に、最上位の要素がbor c（ie D_abc < 0）の場合、bまたはcが一緒に来る場合は、それをスタックにプッシュします（ie D_abc <- D_abc - 1）。それ以外の場合は、最上位の要素をスタックから削除します（ie D_abc <- D_abc + 1）。

上記のルールを使用すると、スタックはD_abc各瞬間のカウントを保持します。これは、文字列を受け入れるか受け入れないかを正確に示す必要があります。したがって、言語は文脈自由であると結論付けることができます。

于 2011-12-10T13:08:03.713 に答える