Context-Free Languages  

 

Part I: Regular Languages

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

1. Given the formal description of NFA M₁ = ({q₁, q₂, q_3, q₄}, Σ, δ, q₁, {q₂, q₄}) where δ is defined below:

δ(q₁, 0) = {q₂}

δ(q₁, ε) = {q₃}

δ(q₂, 1) = {q_1, q₄}

δ(q₃, 0) = {q₂}

δ(q₃, 1) = {q₁}

δ(q₄, 1) = {q₂}

Convert NFA M₁ into a DFA.

2. Consider the description of language L₁.

L₁ = { 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₁.

Show that L₁ is regular.

3. Let L₂ = {0^m1ⁿ | m, n ≥ 0 and m ≠ n}. Use pumping lemma for regular languages to show that L₂ is not regular.

Part II: Context-Free Languages  

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

A → 1B1 | C

B → 0B0 | 1B1 | C

C → 0 | 1 | ε

1. Show that G₁ is ambiguous.
2. (4 Describe the language the G₁ generates in English sentences i.e., what kinds/patterns of strings that it generates.
3. Let the grammar G₂ = ({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.

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

 

 

Part III: Turing Machines  

1. Let L₄ = { w | w is a palindrome whose length is odd and its middle symbol is 1 }. Show that L₄ 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.

1. There must be at least one accepting state in a DFA.
2. Every regular language is context-free.
3. 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.
4. Every context-free language is Turing-recognizable.
5. There can only be one accepting state in a Turing Machine.