patternMinor
Basic doubt in converting PDA to DPDA
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$.
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}$
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.