1
$\begingroup$

I have this NPDA for language L = {w: num_a(w) == num_b(w)}
all loops in q1 a, $ -> 0$ b, $ -> 1$ a, 0 -> 00 b, 1 -> 11 a, 1 -> \lambda b, 0 -> \lambda ------>q1-----------------\lambda, $ -> $------>q2 initial state: q1
final state: q2
What if I modified L such that the number of a's is not equal to number of b's.
That is L' = {w: num_a(w) != num_b(w)}. What would be the modification I have to make in the original NPDA.

$\endgroup$
1
$\begingroup$

Your PDA can act as follows. For each $a$ being read, it pushes $A$ into the stack. Then, for every $b$ being read, it attempts to pop $A$ off the stack. If there are no more $A$s, it moves to an accepting state, checking that the rest of the input consists of $b$s; this handles the case in which there are more $b$s than $a$s. Alternatively, it could decide at some point to move, via an $\epsilon$ transition that pops an $A$, to a different accepting state at which no more symbols can be read; this handles the case in which there are more $a$s than $b$s.

$\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.