0
$\begingroup$

If we want to design a PDA that accepts all words those the first half equals reverse of the second half and there is a '#' between them, "ab#ba" for example.

We start push each letter we read and when we read the symbol '#' don't push it and start popping from its next letter and check for match between the current letter and the top of the stack.

But what do we if there is no '#' symbol in the center of the string, can we do the same of usual NFA ?

I mean can we make same transitions twice, each one to distinct state ?

Example : let us be in the state 'q1', when I read the letter make a transition to the state q2 and pop the top of the stack and make a transition to the state q3 without pop ?

$\endgroup$
0
$\begingroup$

Yes, there are both deterministic and non-deterministic pushdown automata.

Non-determistic pushdown automatons can recognize all context-free languages, while deterministic pushdown automatons con only recognize a proper subset of the context-free languages (these languages are called deterministic context-free languages).

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.