すべての文脈自由文法をNFA/DFAに変換できますか？

Question

私はDFAに文脈自由文法を変換する方法については、この記事を見てきました： Automata theory : Conversion of a Context free grammar to a DFA

しかし、思っ全ての文脈自由文法は、DFA/NFAに変換することができますか？正規表現として表現できない文脈自由文法はどうですか？ Ex。 S - >（S）| （）

ありがとう！

Answer 1

通常の言語のみがDFAに変換され、すべてのCFGが通常の言語を表すわけではありません。

したがって、答えは「いいえ」です。

のNFAはのDFAよりも表現力はないので、あなたはそれが右または左線形である場合

A CFGは正規言語を表しNFAとDFAを置き換える場合は、上記の文はまだ本当だろう。 CFGが左または右リニアでないという事実だけでは何も証明されません。たとえば、S→a | a S aは、S→a | S a aと同じ言語を生成します。