1

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!

Community
  • 1
  • 1
ssssay
  • 58
  • 1
  • 6

1 Answers1

1

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.

rici
  • 219,119
  • 25
  • 219
  • 314
  • http://hackingoff.com/images/basic-bottom-up-parser/2016-12-13_18-37-59_-0800-dfa.svg Just come across this and now a bit confused about DFA for LR(0) parser. Is DFA for LR(0) parser a conversion for context free grammar? Or is it just helps building LR(0) parser (got multiple finishing states)? – ssssay Dec 14 '16 at 02:43
  • @ssssay: Although that page describes its graph as a DFA, what drives the LR parser is really a PDA (pushdown automaton) which is not F (finite). The push transitions are not shown, and the "accepting" states are actually pop transitions (which can't be graphed because they depend on the contents of the stack at that point). It's easy to see that that is the case; you only have to try to actually process an input using that machine. (And also, not all CFGs are LR(0) or even LR(k). ) – rici Dec 14 '16 at 04:13