Let's construct a nondeterministic pushdown automaton $M=(,,Q,,q)$ that accepts the set Lsube$\{0,1{\}}^{**}$ of all binary palindromes with an even length. Palindrome is a string that reads the same backward as forward, e$.$g$.,"1001".$ So $L=\{w{w}^R|win\{0,1{\}}^{**}\},$ where $w^R$ is the reverse of $w.$

We have tape alphabet $=\{0,1\},$ stack alphabet $=\{$$$,0,1\},$ and state set $Q=\{q,q_1\}.$

Since we only care about binary palindromes with an even length, the idea is to maintain two states where the first state $q($which is also the start state$)$ means we are scanning the first half of the input string and the second state $q_1$ means we are scanning the second half of the input string. We push every symbol read from the tape into the stack when we are at state $q.$ We use the nondeterminism to guess the middle of the input string. So$,$ we also switch to the other state $q_1$ when we are at state $q$ and read a symbol from the tape.

$2/7$

CS$3240$ Assignment $2$

Yiming Zhao

When we are at state $q_1,$ we check whether the current symbol read from the tape is the same as the symbol on the top of the stack. If so$,$ we keep moving the tape head and pop up the top element of the stack. Otherwise, we have a mismatch and reject the input.

The transition function $$ is specified by the following instructions. But some instructions are missing. Please complete this machine by adding those missing transitions. Please just use the notation defined above.

$q00qR00$

$q00q_{1}R00$

$q01qR10$

$q01q_{1}R10$

$q0$$$qR$$$0$

$q0$$$q_{1}R$$$0$

$q10qR01$

$q10q_{1}R01$

$q11qR11$

$q11q_{1}R11$

$q1$$$qR$$$1$

$q1$$$q_{1}R$$$1$

$q1qN1$

$q_{1}00q_{1}Rlon$

$q_{1}01q_{1}N1$

$q_{1}0$$$q_{1}N$$

$q_{1}10q_{1}N0$

$q_{1}1$$$q_{1}N$$

$q_{1}0q_{1}N0$

$q_{1}1q_{1}N1$