COS3701
Assignment
3
USER
[Email address]
, COS3701 Assignment 3 (COMPLETE ANSWERS) 2025 - DUE 2025;. Question 1 [10] Given
that L1 = (aa)* and L2 = (a + b)*ab(a + b)*. Find grammars for L1 and L2. Then use Theorem
37 to find L1L2. Question 3 [10] Using theorem 42 algorithm to determine whether the
following grammar generate any words. S AB A BC C DA B CD D a A b Look at the
reformulated version of Theorem 42 in your online study units Question 4 [15] Build a Turing
Machine (TM) that • accepts all words in {an bn am | n ≥ 0; m > n} • loops forever on all words
starting with b, and • rejects all other words. Assume that the alphabet is Σ = {a, b} Question 5
[15] Build a 2PDA that accepts the language {a2nbnanb2n | n > 0}.
Question 1 [10 Marks]
Given:
L₁ = (aa)*
L₂ = (a + b)ab(a + b)
(a) Grammar for L₁ = (aa)*
L₁ consists of strings made up of even numbers of a's, i.e. 0 or more repetitions of “aa”.
CFG G₁ for L₁:
S₁ → ε
S₁ → aa S₁
(b) Grammar for L₂ = (a + b)ab(a + b)
This language includes all strings over {a, b} that contain the substring ab.
CFG G₂ for L₂:
S₂ → A a b B
A → ε | a A | b A
B → ε | a B | b B
(c) Grammar for L₁L₂ using Theorem 37
Theorem 37:
Let G₁ and G₂ be CFGs for L₁ and L₂. A grammar G for L₁L₂ is given by:
Assignment
3
USER
[Email address]
, COS3701 Assignment 3 (COMPLETE ANSWERS) 2025 - DUE 2025;. Question 1 [10] Given
that L1 = (aa)* and L2 = (a + b)*ab(a + b)*. Find grammars for L1 and L2. Then use Theorem
37 to find L1L2. Question 3 [10] Using theorem 42 algorithm to determine whether the
following grammar generate any words. S AB A BC C DA B CD D a A b Look at the
reformulated version of Theorem 42 in your online study units Question 4 [15] Build a Turing
Machine (TM) that • accepts all words in {an bn am | n ≥ 0; m > n} • loops forever on all words
starting with b, and • rejects all other words. Assume that the alphabet is Σ = {a, b} Question 5
[15] Build a 2PDA that accepts the language {a2nbnanb2n | n > 0}.
Question 1 [10 Marks]
Given:
L₁ = (aa)*
L₂ = (a + b)ab(a + b)
(a) Grammar for L₁ = (aa)*
L₁ consists of strings made up of even numbers of a's, i.e. 0 or more repetitions of “aa”.
CFG G₁ for L₁:
S₁ → ε
S₁ → aa S₁
(b) Grammar for L₂ = (a + b)ab(a + b)
This language includes all strings over {a, b} that contain the substring ab.
CFG G₂ for L₂:
S₂ → A a b B
A → ε | a A | b A
B → ε | a B | b B
(c) Grammar for L₁L₂ using Theorem 37
Theorem 37:
Let G₁ and G₂ be CFGs for L₁ and L₂. A grammar G for L₁L₂ is given by:
