一連の入力記号 Σ={a,b} 、L={ε,a,abbb,aabbbbbbbbb,aaabbbbbbbbbbbbbbbbbb,...} を想定します。
次に、上記の言語の有限オートマトン (つまり、単純な算術等比数列を形成する) はどうなるでしょうか?
1 に答える
2
これは非正規言語の良い例です。直観的に、有限メモリ コンピューターが文字列が言語に含まれているかどうかを判断するには、b の数が正しいかどうかを判断できるように、a の数を覚えておく必要があります。残念ながら、a の数には無限に多くの可能な選択肢があり、有限オートマトンは無限に多くの異なる選択肢の 1 つを覚えることができません。
これは、正規言語のポンピング補題または Myhill-Nerode の定理を使用して正式に証明できます。ポンピング補題を使用して、a 3n+1 b 3 nのような文字列を選び、aの数をポンピングすると、b の数への接続が切断されることを示します。Myhill-Nerode の定理では、a 3n+1の形式の文字列の無限族を選択し、1 つの文字列に適切な数の b を追加すると、他の文字列が言語にないものになることを示してください。
于 2016-08-07T06:53:55.777 に答える