2
$\begingroup$

The language is:

a^nb^m where n = m or n = m+2

My solution is that I push a's into the stack till b is encountered. When b is encountered, I pop out the a's.

If at the end of the input, the stack is empty then string is accepted. Transition for this is

delta (lambda, z) = (q, lambda)

delta (b,a) = (q, lambda)

If at the end of the input, the stack has aa, then the string is accepted. Transition for this is

delta (lambda, aa) = (q, lambda)

z is the initial stack symbol. From the above two transitions, it seems non-deterministic but intuitively it should be deterministic because there is never a choice - either stack is empty or stack has aa.

How do I represent this DPDA properly?

Notation used is as per Peter Linz fourth edition - Introduction to formal languages.

$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Just have different states for reading the first three $\mathtt a$'s and push different symbols for them. Then when you reach the end of the input it's easy to check whether you're looking at one of the special first-three-symbols.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .