Assignment: 1 (TOA)
Name: Muhamamd Maroof
Roll Number: mtf25005142
Course Instructor: Miss Iqra
Part A: Regular Expressions
Write a Regular Expression (RE) for each of the following languages over Σ = {a, b}:
1. Strings that contain exactly two a’s.
b*ab*ab*
2. Strings that start and end with the same symbol.
a+b+(a(a+b)*a)+(b(a+b)*b)
3. Strings where no two consecutive b’s appear.
(a+ba)*(b+ϵ)
4. Strings where every a is immediately followed by b.
(b+ab)*
5. Strings of length divisible by 3.
(a+b)3n
Part B: Construct & Draw Automata
Construct NFAs for the following languages and draw their state diagrams:
• L₁ = { w ∈ {a,b}* | w ends with “ab” }
• L₂ = { w ∈ {0,1}* | w starts with “1” and ends with “0” }
• L₃ = { w ∈ {a,b}* | w contains substring “aa” }
Convert the NFA of L₁ into an equivalent DFA using subset construction. Show all intermediate state subsets,
identify final states, and draw the DFA.
Draw DFA diagrams for the following languages:
• All strings over {a, b} where the number of a’s is even.
• All strings where the third symbol from the right is b.
• All strings that do not contain substring “bb”.
Part C: Conversion Practice
a. Convert the Regular Expression (a + b)*abb into an equivalent NFA using
Thompson’s construction.
b. Convert the same NFA into a DFA using the subset method.
1. ε-closure({1}) = {1,2,3,5} = S0 ← this is the DFA start-state
2. ε-closure({4}) = {4,7,8} = S1
3. ε-closure({6}) = {6,7,8} = S2
4. ε-closure({9}) = {9} = S3
5. ε-closure({10}) = {10} = S4
6. ε-closure({11}) = {11} – S5
7. ε-closure(∅) = ∅ =S_Dead Trap State
From a b
S0 = {1,2,3,5} S1 = {4,7,8} S2 = {6,7,8}
S1 = {4,7,8} S3 = {9} S_Dead = ∅
S2 = {6,7,8} S3 = {9} S_Dead = ∅
S3 = {9} S_Dead = ∅ S4 = {10}
S4 = {10} S_Dead = ∅ S5 = {11}
S5 = {11} S_Dead = ∅ S_Dead = ∅
S_Dead = ∅ S_Dead = ∅ S_Dead = ∅
c. Minimize the DFA obtained above and draw the minimized DFA.
S1 and S2 share common behavior, {7,8}. They can be combined as one state.
So now S1 {4,6,7,8} = S1 U S2
From a b
S0 S1 S1
S1 S2 S_Dead = ∅
S2 S_Dead = ∅ S3
S3 S_Dead = ∅ S4
S4 S_Dead = ∅ S_Dead = ∅
S_Dead = ∅ S_Dead = ∅ S_Dead = ∅
Part D: Induction Proof
Prove by mathematical induction that: For every n ≥ 0, the number of strings of length n over the alphabet {0,1} is
2ⁿ.
Proof (by Mathematical Induction)
We want to prove that for every n ≥ 0, the number of binary strings (made up of 0’s and 1’s) of length n is 2n
Base Case (n = 0):
If the string length is 0, the only possible string is the empty string (no symbols at all).
So there is exactly 1 string.
Now, 20 = 1, which matches our count. Hence, the statement is true for n=0.
Inductive Step:
Now assume that for some integer k ≥ 0, the statement holds true that is, there are 2k binary strings of length k.
We must show it’s also true for k+1.
To make a string of length k+1, take any string of length k and add one more symbol (either 0 or 1) at the end.
Each of the 2k strings of length k can become two different strings of length k+1:
one ending with 0, and one ending with 1.
So the total number of strings of length k+1 will be:
2×2k=2k+1
Conclusion:
Since the base case is true and the truth of n=k implies the truth of n=k+1, by mathematical induction, the
formula
Number of binary strings of length n = 2n
holds for all n ≥ 0.
Part E: Bonus Section
Design a single DFA that accepts all strings over {a,b} where:
• The number of a’s is even,
• The string ends with “ab”.
Draw the DFA clearly and label each state to indicate its logical meaning.
