なぜ{a^nb^n |ですn> = 0}通常はありませんか？

Question

CSコースには、通常のない言語の例があります。

{a^nb^n | n >= 0}

メモリコンポーネントがないため、この入力を検証および受け入れる有限状態の状態/マシンを書くことができないため、定期的ではないことを理解できます。 （私が間違っている場合は私を修正してください）

通常の言語のウィキペディアエントリ また、この例をリストしますが、（数学的な）証拠が定期的でない理由を提供しません。

誰かがこれについて私に啓発し、これを証明することもできますか、それとも私も良いリソースを指示しますか？

Answer 1

あなたが探しているのはです 通常の言語のための補題をポンピングします.

これが次のとおりです 例 あなたの正確な問題で：

例：
l = {a^mb^m | M≥1}。
その後、Lは規則的ではありません。
証明：補助補助補給のようにnとします。
w = aとしますⁿbⁿ.
w = xyzと同じように補題をポンピングします。
したがって、xy²z∈L、ただし、xy²zにはBよりも多くのAが含まれています。

Answer 2

「A」記号と「B」記号の同一のシーケンスを「カウント」する有限状態マシンを書くことができないからです。一言で言えば、FSMは「カウント」できません。そのようなFSMを想像してみてください：シンボル「A」にいくつの州を与えますか？ 「b」にいくつですか？入力シーケンスにもっと多くの場合はどうなりますか？

n <= xがxを使用していた場合、整数値を備えている場合は、そのようなFSMを準備できます（多くの状態を持つが、まだ有限数を持つことにより）。そのような言語は規則的です。

Answer 3

有限状態オートマトンには、自動を押し下げる場合のように、データ構造（スタック） - メモリがありません。ええ、それはあなたにいくつかの 'aがいくつかの' bを続けることができますが、「a」の正確な量ではなく、その後の「b」が続きます。

Answer 4

その理由は、NO。 「A」といいえ。 「b」は入力文字列で等しくなります。そして、それを行うには、両方を数えなければなりません。 「a」とno。 「b」の値は、「n」の値が無限に達する可能性があるため、有限のオートマトンを使用して無限にカウントすることはできません。

だから{a^nb^n | n> = 0}は規則的ではありません。