2.31


2.35


Here is a CFG for palindromes

S -> 0S0 | 1S1 | 0 | 1 | ""

Convert this CFG into a PDA.


Here is a PDA for palindromes

s0 -> 0s
s1 -> 1s
s -> a
s0 -> a
s1 -> a
0a0 -> a
1a1 -> a
a is accepting

Convert this PDA into a CFG.


Using Turing.java, write a program to accept ww over { 0, 1 }.
Put it into your account in ww.txt.


3.6


3.15 b


3.16 d