$1.$

Give context$-$free grammars that generate the following languages. In all parts, the alphabet $\backslash$Sigma is $\{0,1\}.$

a$.\{$w$|$ w starts and ends with the same symbol$\}$

b$.\{$w$|$ w $=$ wR$,$ that is$,$ w is a palindrome$\}$

$2.$

Give a context$-$free grammar that generates the language

A $=\{$aibjck$|$ i $=$ j or j $=$ k where i$,$ j$,$ k $>=0\}.$ Is your grammar ambiguous? Why or why not?

$3.$

Convert the following CFG into an equivalent CFG in Chomsky normal form. A $->$ BAB $|$ B $|\backslash$epsi B $->00|\backslash$epsi

$4.$

Design a pushdown automaton that accepts the language $\{0$n$1$n $|$ n $>=0\}.$ In other words, the language consists of all strings that start with zero, followed by an equal number of ones.

a$.$ Draw the transition diagram for the PDA.

b$.$ Show the stack changes for each input symbol.

c$.$ Test your PDA on at least five sample strings and show the step$-$by$-$step process of accepting or rejecting each of them.