SOLVED COMP 335 – Introduction to Theoretical Computer Science Assignment 5

  1. [10 Points] Show that following grammar G, where S is the starting variable, is ambiguous. S → AB | aaaB, A → a | Aa, B → b. 2. [10 Points] A context-free grammar G = ⟨V, T, S, P⟩ is said to be a simple grammar or s-grammar if all its productions are of the form A → ax, where A ∈ V, a ∈ T, x ∈ V ⋆ , and any pair (A, a) occurs at most once in P. Find an s-grammar for L = {a n b 2n : n ≥ 1}. 3. [10 Points] Give an NPDA with 2 states that accepts L = {a n b n+1 : n ≥ 0}. 4. [20 Points] For each of the following CFLs, give a “direct” design of an NPDA. That is, it is not acceptable to first find a CFG and then convert it into an NPDA. (a) L1 = {a n b 2n+1 : n ≥ 0} (b) L2 = {w ∈ {a, b} ⋆ : na(w) ≤ 3nb(w)} 5. [20 Points] Show that the following CFLs are deterministic. (a) L1 = {(ab) n b(ba) n : n ≥ 0} ∪ {(ab) n b : n ≥ 0} (b) L3 = {w ∈ (a, b) ⋆ : na(w) ̸= nb(w)}