BTE2601 Assignment 2 Due 14 July 2025

BTE2601
Assignment 2
Due 14 July 2025

,COS3761

Assignment 3

Due: July 2025

Question 1 [10 Marks]


✍️Task:


Given:

 L1=(aa)∗L_1 = (aa)^*L1=(aa)∗: strings with even numbers of a's
 L2=(a+b)∗ab(a+b)∗L_2 = (a + b)^*ab(a + b)^*L2=(a+b)∗ab(a+b)∗: strings
containing substring "ab"
Find grammars for L1L_1L1 and L2L_2L2, then use Theorem 37 to construct a
grammar for L1L2L_1L_2L1L2




1.1 Grammar for L1=(aa)∗L_1 = (aa)^*L1=(aa)∗

This language includes:

 ε,aa,aaaa,aaaaaa,…\varepsilon, aa, aaaa, aaaaaa, \dotsε,aa,aaaa,aaaaaa,…
 Each string contains even numbers of a's

CFG for L1L_1L1:

 V1={S1}V_1 = \{S_1\}V1={S1}
 Σ1={a}\Sigma_1 = \{a\}Σ1={a}
 P1:S1→aaS1∣εP_1: S_1 \rightarrow aaS_1 \mid \varepsilonP1:S1→aaS1∣ε
 Start symbol: S1S_1S1

, Sample derivations:

 S1⇒εS_1 \Rightarrow \varepsilonS1⇒ε
 S1⇒aaS1⇒aaε=aaS_1 \Rightarrow aaS_1 \Rightarrow aa\varepsilon = aaS1
⇒aaS1⇒aaε=aa
 S1⇒aaS1⇒aaaaS1⇒aaaaε=aaaaS_1 \Rightarrow aaS_1 \Rightarrow aaaaS_1
\Rightarrow aaaa\varepsilon = aaaaS1⇒aaS1⇒aaaaS1⇒aaaaε=aaaa

Language: all strings with even a’s

1.2 Grammar for L2=(a+b)∗ab(a+b)∗L_2 = (a + b)^*ab(a + b)^*L2=(a+b)∗ab(a+b)∗

Language contains any string over {a,b}\{a, b\}{a,b} with at least one "ab" substring.

CFG for L2L_2L2:

 Variables: {S2,T}\{S_2, T\}{S2,T}
 Alphabet: {a,b}\{a, b\}{a,b}
 Productions:
o S2→aS2∣bS2∣aTS_2 \rightarrow aS_2 \mid bS_2 \mid aTS2→aS2∣bS2∣aT
o T→bT∣aT∣εT \rightarrow bT \mid aT \mid \varepsilonT→bT∣aT∣ε

Explanation:

 S2S_2S2: builds the prefix until the "a" starting the "ab"
 aTaTaT: ensures "ab" pattern
 TTT: completes the suffix (any string)

Sample:

 S2⇒aT⇒abT⇒abaT⇒abaS_2 \Rightarrow aT \Rightarrow abT \Rightarrow abaT
\Rightarrow abaS2⇒aT⇒abT⇒abaT⇒aba

Language: strings with substring "ab" like ab, aab, babab, etc.