Problem
Construct non-deterministic pushdown automata (PDA) to accept the following languages. (Note: there is NO unique answer for each question. PDA accept a string if, after processing the string, the stack is empty, and it is in a final state. PDA can be deterministic. In this course, we only require non-deterministic PDA, so the sink state is not necessary in construction.)
• L = {wwR | w = (a+b)+}, wR is the reverse of w.
• L = {w#wR | w is any binary string}, wR is the reverse of w.
• L = {binary strings in the form 0n1m0n, where n >= 1, and m >= 1}.