COS3701
EXAM PACK
, lOMoARcPSD|18222662
COS3701 Oct/Nov 2024
Question 1 [16]
a) Determine a regular expression for the language L over the alphabet {a; b} that
consists of all words that have at least one a but contain exactly one bb substring (and
no other as). Example of words in the language are bba, aaabbaaa, aaaabbaaaaaa
etc. Examples of words that are not in the language are b, a, bab, ab, aaabbbb,
abaaabaaaaa etc. (2)
b) Design a deterministic finite automaton (DFA) that will recognise all of the words in
L as defined above. (4)
c) Use Theorem 21 to develop a context-free grammar (CFG) for the language L.
(4)
d) Convert the following CFG to Chomsky Normal Form (CNF):
S -> aXY | Yb
X -> XZYZ | a
Y -> bY | Λ
Z -> a | Λ (6)
Question 2 [12]
Build a deterministic pushdown automata (DPDA) that accepts the language L =
{(ab)n(aa)m(ba)n-1 | n ≥1;m ≥1} over the alphabet ∑ = {a; b}.
Question 3 [10]
The pumping lemma with length for context-free languages (CFLs) can be stated as follows:
Let L be a CFL generated by a CFG in CNF with p live productions.
Then any word w in L with length > 2 p can be broken into five parts:
w = uvxyz
such that
length(vxy) ≤ 2p
length(x) > 0
length(v) + length(y) > 0
and such that all the words uv nxynz with n ∈{2, 3, 4,…} are also in the language L.
Use the pumping lemma with length to prove that the language
L = {(a)n(b)2n+2(a)n-1 |n ≥ 1}
over the alphabet ∑ = {a, b} is non-context-free.
2
, lOMoARcPSD|18222662
COS3701 Oct/Nov 2024
Question 4 [6]
Use the reformulated version of Theorem 42 to decide whether the grammar given below
generates any words:
S -> XY
X -> SY
Y -> SX
X -> a
Y -> b
Question 5 [6]
Consider the Turing Machine (TM) T (over the input alphabet ∑ = {a; b}) given below.
a) What is the shortest word that would be accepted by T ? (1)
b) What is accept(T )? (2)
c) What is reject(T )? (2)
d) What is loop(T )? (1)
Question 6 [14]
Build a Turing Machine (TM) that
• accepts all words in {(b)n+2an | n ≥ 1},
• loops forever on all words starting with a, and
• rejects all other words.
Assume that the alphabet is ∑ = {a; b}.
3
, lOMoARcPSD|18222662
COS3701 Oct/Nov 2024
Question 7 [12]
Build a 2PDA that accepts the language
L = {anb2na2nbn| n >0}
over the input alphabet ∑ = {a; b}
Question 8 [4]
Draw a summary table for the TM below
@unisa
2024
4
EXAM PACK
, lOMoARcPSD|18222662
COS3701 Oct/Nov 2024
Question 1 [16]
a) Determine a regular expression for the language L over the alphabet {a; b} that
consists of all words that have at least one a but contain exactly one bb substring (and
no other as). Example of words in the language are bba, aaabbaaa, aaaabbaaaaaa
etc. Examples of words that are not in the language are b, a, bab, ab, aaabbbb,
abaaabaaaaa etc. (2)
b) Design a deterministic finite automaton (DFA) that will recognise all of the words in
L as defined above. (4)
c) Use Theorem 21 to develop a context-free grammar (CFG) for the language L.
(4)
d) Convert the following CFG to Chomsky Normal Form (CNF):
S -> aXY | Yb
X -> XZYZ | a
Y -> bY | Λ
Z -> a | Λ (6)
Question 2 [12]
Build a deterministic pushdown automata (DPDA) that accepts the language L =
{(ab)n(aa)m(ba)n-1 | n ≥1;m ≥1} over the alphabet ∑ = {a; b}.
Question 3 [10]
The pumping lemma with length for context-free languages (CFLs) can be stated as follows:
Let L be a CFL generated by a CFG in CNF with p live productions.
Then any word w in L with length > 2 p can be broken into five parts:
w = uvxyz
such that
length(vxy) ≤ 2p
length(x) > 0
length(v) + length(y) > 0
and such that all the words uv nxynz with n ∈{2, 3, 4,…} are also in the language L.
Use the pumping lemma with length to prove that the language
L = {(a)n(b)2n+2(a)n-1 |n ≥ 1}
over the alphabet ∑ = {a, b} is non-context-free.
2
, lOMoARcPSD|18222662
COS3701 Oct/Nov 2024
Question 4 [6]
Use the reformulated version of Theorem 42 to decide whether the grammar given below
generates any words:
S -> XY
X -> SY
Y -> SX
X -> a
Y -> b
Question 5 [6]
Consider the Turing Machine (TM) T (over the input alphabet ∑ = {a; b}) given below.
a) What is the shortest word that would be accepted by T ? (1)
b) What is accept(T )? (2)
c) What is reject(T )? (2)
d) What is loop(T )? (1)
Question 6 [14]
Build a Turing Machine (TM) that
• accepts all words in {(b)n+2an | n ≥ 1},
• loops forever on all words starting with a, and
• rejects all other words.
Assume that the alphabet is ∑ = {a; b}.
3
, lOMoARcPSD|18222662
COS3701 Oct/Nov 2024
Question 7 [12]
Build a 2PDA that accepts the language
L = {anb2na2nbn| n >0}
over the input alphabet ∑ = {a; b}
Question 8 [4]
Draw a summary table for the TM below
@unisa
2024
4
