**Part ****I: Regular Languages **

For all questions in Part 1, Σ = {0, 1}.

- Given the formal description of NFA
*M*_{1 }= ({q_{1}, q_{2}, q_{3, }q_{4}}, Σ, δ, q_{1}, {q_{2}, q_{4}}) where δ is defined below:

δ(q_{1}, 0) = {q_{2}}

δ(q_{1}, ε) = {q_{3}}

δ(q_{2}, 1) = {q_{1, }q_{4}}

δ(q_{3}, 0) = {q_{2}}

δ(q_{3}, 1) = {q_{1}}

δ(q_{4}, 1) = {q_{2}}

Convert NFA *M*_{1 }into a DFA.

- Consider the description of language
*L*_{1}.

*L*_{1 }= { *w *| *dec(w) *≠ 0 and *dec(w) *is divisible by 5 }

where *dec(w) *is an equivalent decimal value (base 10) of the given binary encoded string. For instance, 0, 101, 1010, 1111, and 10100 ∈ *L*_{1}*. *

Show that *L*_{1 }is regular.

- Let
*L*_{2 }= {01^{m}| m, n ≥ 0 and^{n }*m*≠*n*}. Use pumping lemma for regular languages to show that*L*_{2 }is not regular.

**Part ****II: Context-Free Languages **

- Let the grammar
*G*_{1 }= ({A, B, C}, {0, 1}, R, A) where R is defined below.

A → 1B1 | C

B → 0B0 | 1B1 | C

C → 0 | 1 | ε

- Show that
*G*_{1 }is ambiguous. - (4 Describe the language the
*G*_{1 }generates in English sentences*i.e.*, what kinds/patterns of strings that it generates. - Let the grammar
*G*_{2 }= ({S, A, B}, {0, 1}, R, S) where R is defined below.

S → 01S | 0A

A → 1A | B | ε

B → 00 | ε

Give a corresponding grammar in Chomsky Normal Form.

- Let
*L*_{3 }= {*a*^{m}*b*^{n}*c*|^{2m-n }*m*> 0 and*n*≥ 0 }. Show that*L*_{3 }is context-free.

**Part ****III: Turing Machines **

- Let
*L*_{4 }= {*w*|*w*is a palindrome whose length is odd and its middle symbol is 1 }. Show that*L*_{4 }is Turing-decidable. Recall that a palindrome is a string that reads the same way in both forward and backward directions*i.e.*,*w*=*w*^{R}.

**Part ****IV****: True/False **

Determine whether each of the following statements is *true *or *false *based on Sipser’s book. Justify your answers; otherwise, you will not receive any credits. You can refer to any theorems to support your answers.

- There must be at least one accepting state in a DFA.
- Every regular language is context-free.
- The class of regular language is closed under difference operation (–). Note that – is the binary operation on sets such that A–B yields the set of all strings that are in A but not in B.
- Every context-free language is Turing-recognizable.
- There can only be one accepting state in a Turing Machine.