$L = \{ 0^i 1^j 2^k \mid i = 2j \text{ or } i = k, \text{ where } i,j,k \geq 1 \}$
I have trouble about this PDA. Anybody can help me about draw this PDA?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The PDA should start by counting the numbers of $0$s (by pushing some symbol onto the stack for each $0$ encountered) ensuring that there is at least one $0$. Then, nondeterministically choose to match each $0$ with two $1$s (by popping one symbol off the stack for every two $1$s encountered) or, ignore any $1$s encountered and match each $0$ with a $2$ (by popping one symbol from the stack for each $2$ encountered).
