COS3701
ASSIGNMENT 3 2026
UNIQUE NO:
DUE DATE:
, THEORETICAL COMPUTER SCIENCE III - COS3701
ASSIGNMENT 3 2026
Question 1 [10]
Let $L_1$ be the grammar generating $(a+b)^{*}$. Let $L_2$ be the grammar
generating $(aa)^{*}b(a+b)^{*}$. First, provide the grammars generating $L_1$ and
$L_2$ respectively. Then apply the applicable theorem from Chapter 17 (Theorem 36)
to determine $L_1 + L_2$.
CFG generating $L_1$:
$$S \rightarrow aS \mid bS \mid \Lambda$$
CFG generating $L_2$:
$$S \rightarrow XbY$$
$$X \rightarrow aaX \mid \Lambda$$
$$Y \rightarrow Ya \mid Yb \mid \Lambda$$
Applying Theorem 36 to find a CFG for $L_1 + L_2$: First, rewrite the
grammar for $L_1$ using a distinct start symbol $S_1$:
$$S_1 \rightarrow aS_1 \mid bS_1 \mid \Lambda$$
And keep the grammar for $L_2$ with start symbol $S_2$:
$$S_2 \rightarrow XbY$$
$$X \rightarrow aaX \mid \Lambda$$
$$Y \rightarrow Ya \mid Yb \mid \Lambda$$
ASSIGNMENT 3 2026
UNIQUE NO:
DUE DATE:
, THEORETICAL COMPUTER SCIENCE III - COS3701
ASSIGNMENT 3 2026
Question 1 [10]
Let $L_1$ be the grammar generating $(a+b)^{*}$. Let $L_2$ be the grammar
generating $(aa)^{*}b(a+b)^{*}$. First, provide the grammars generating $L_1$ and
$L_2$ respectively. Then apply the applicable theorem from Chapter 17 (Theorem 36)
to determine $L_1 + L_2$.
CFG generating $L_1$:
$$S \rightarrow aS \mid bS \mid \Lambda$$
CFG generating $L_2$:
$$S \rightarrow XbY$$
$$X \rightarrow aaX \mid \Lambda$$
$$Y \rightarrow Ya \mid Yb \mid \Lambda$$
Applying Theorem 36 to find a CFG for $L_1 + L_2$: First, rewrite the
grammar for $L_1$ using a distinct start symbol $S_1$:
$$S_1 \rightarrow aS_1 \mid bS_1 \mid \Lambda$$
And keep the grammar for $L_2$ with start symbol $S_2$:
$$S_2 \rightarrow XbY$$
$$X \rightarrow aaX \mid \Lambda$$
$$Y \rightarrow Ya \mid Yb \mid \Lambda$$
