finite-automata - 規則的ではないコンテックスフリーとはどういう意味ですか

Question

試験のために文脈自由文法を準備しています。なぜその言語なのか理解できなかった

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

は文脈自由ですが、規則的ではありません。なぜ定期的ではないのですか？式が正規でないと言えるのはいつですか?

ありがとう

Answer 1

前の回答で述べたように、文脈自由文法で表現できるため、文脈自由です。

例: S -> aSb | ε

有限状態マシンや正規表現で表現できないため、正規ではありません。As の数を数えて、B の数が一致することを確認できるはずです。nは何でもよいため、これは有限状態では実行できません。

Answer 2

正規表現または (同等の)有限状態マシンによって (正確に) 一致できない場合、その式は正規ではありません。文脈自由言語と正規言語も参照してください。

Answer 3

標準的なアプローチは、PumpingLemmaを使用することです。

Answer 4

文脈自由文法を使用して表現できるため、文脈自由であると言えます。ただし、正規表現 (および有限オートマトン) はその言語を表すことができないため、正規ではありません。