Reference no: EM13843974

Problem 1: Prove using the pumping lemma and closure properties that the languages below are not regular. You can use the game argument provided in class.

Prove using the pumping lemma and closure properties that the languages below are not regular.

1. L₁ = {0ⁿ10ⁿ | n ≥ 0}. The alphabet is Σ = {0,1}.

2. L₂ = {0^m10ⁿ | m ≥ n}. The alphabet is Σ = {0,1}.

3. Let Σ be {0,1}. Show that L₃ = {ω) ∈ Σ* |ω is a palindrome} is not regular. A palindrome is a string that reads the same forward as backwards.

4. L₄ = {0ⁿ | n is a prime number}. The alphabet is Σ = {0}.

5. L₅ = {0^m10ⁿ | m ≥ n} (Hint: Relate ^-L₅ to L₂ and argue using a closure property). The alphabet is Σ = {0,1}.

6. L₆ : {0^m10ⁿ | m - n = 5, n ≥ 0}. The alphabet is Σ = {0,1}.

Problem 2 Provide a context free grammar for the languages L₁, L₂, L₃ and L6 in problem 1 above.

Problem 3 Show that the following language is context free:

L₆ : {x ∈ Σ^* | x cannot be written as ww for any ω ∈ Σ*}