HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Basic doubt in converting PDA to DPDA

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
doubtdpdapdaconvertingbasic

Problem

This is the PDA to accept strings with equal number of $a$'s and $b$'s. The $\epsilon$ transition in the first state is causing nondeterminism.
When we have input a with Z at the bottom of the stack, then at the beginning it can do $(a,Z/aZ)$ or $(\epsilon,Z/Z)$ and go to final state, so automaton has 2 choices which can lead to 2 different states.

How do I convert it to DPDA ? How do I remove that $\epsilon$ transition from first state to make the PDA deterministic?

Here, the stack symbol is $Z$ and the transition $(a,Z/aZ)$ means on seeing input $a$ with $Z$ at the top of the stack, push $aZ$.

Solution

The DPDA could be constructed by adding explicit states and dropping too permisive epsilon transition.

I will denote accepting state by paranthesis around the name.

$(q_0, \epsilon, Z, (q_f), Z) \text{ accept empty string}$

$((q_f), a, Z, q_a, a)\text{ add initial a (or after cancellation occurs)}\\
((q_f), b, Z, q_b, b)\text{ add initial b (or after cancellation occurs)}\\
(q_a, b, a, q_a, \epsilon) \text{ even out two symbols}\\
(q_b, a, b, q_b, \epsilon) \text{ even out two symbols}\\
(q_a, \epsilon, Z, (q_f), Z) \text{ accept, it happens only with empty stack}\\
(q_b, \epsilon, Z, (q_f), Z) \text{ accept, it happens only with empty stack}\\
(q_a, a, a, q_a, aa)\text{ add another a to stack}\\
(q_b, b, b, q_b, bb)\text{ add another b to stack}$

Context

StackExchange Computer Science Q#87513, answer score: 2

Revisions (0)

No revisions yet.