[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)}