parsingcontext-free-grammardfanfa

Can all context free grammars be converted to NFA/DFA?

I've seen this post about how to convert context free grammar to a DFA: Automata theory : Conversion of a Context free grammar to a DFA

However, just wondering can all context free grammars be converted to DFA/NFA? What about context free grammars that cannot be expressed as a regular expression? Ex. S->(S) | ()

Thanks!

Solution

  • Only regular languages can be converted to a DFA, and not all CFGs represent regular languages, including the one in the question.

    So the answer is "no".

    NFAs are not more expressive than DFAs, so the above statement would still be true if you replaced DFA with NFA

    A CFG represents a regular language if it is right- or left-linear. But the mere fact that a CFG is not left- or right-linear proves nothing. For example, S→a | a S a happens to generate the same language as S→a | S a a.