6
$\begingroup$

Both Deterministic and Non deterministic Finite Automata can recognize the same universe of regular languages. On the other hand, Deterministic Push Down Automata can only recognize a subset of context free languages that Non deterministic Push Down Automata can recognize. Is there any intuitive reason for this? It would seem that NFA's should be more powerful than DFA's but they turn out to be equivalent

$\endgroup$
  • 4
    $\begingroup$ My completely informal intuition was that PDAs have unbounded state space via the stack (like TMs have unbounded states via the tape) and somehow this means that the powerset-like construction used to convert NFAs to DFAs doesn't work. $\endgroup$ – mhum Mar 8 '17 at 1:18
  • $\begingroup$ @user13972 Agreed. It was purely an informal gut feeling without really any solid grounding. $\endgroup$ – mhum Mar 8 '17 at 22:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.