1) Convert the following nondeterministic finite automaton to equivalent deterministic finite automaton. If there are any useless states created in the conversion process, eliminate them.
2) Convert the following finite automaton to regular expression. Please first construct an equivalent GNFA (generalized nondeterministic finite automaton). Then eliminate states.
3) Give implementation-level descriptions of Turing machine that decides the following language over the alphabet {a, b} {w | w contain equal number of a's and b's}
4) Give a context free grammar G that generates the language over alphabet {a, b, c}
L(G) = {ai bj ck | i = j or j = k where i, j, k >= 0}
5) Give an informal description of a pushdown automaton that recognizes the following language A = {ai bj ck | i = j or i = k where i, j, k >= 0}
6) Give the state diagram of PDA that recognizes the language in question 6.
7) Convert the following CFG into an equivalent CFG in Chomsky normal form. Alphabet is {0, 1}
X à 0 X 1 | 0 1
What is the language of this grammar?