State Input 0 Input 1
Q1 (a) - Kleene Closure and Difference Between L and L+* q0 q1 q2
q1 Dead q2
Definition of Kleene Closure q2 q1 Dead
• The Kleene Star (denoted as L*) of a language L represents zero or more repetitions of Dead Dead Dead
strings in L.
• The Positive Closure (denoted as L+) represents one or more repetitions of strings in L.
Regular Expression
(0|1)(01|10)*
Given L = {ab, aa, baa}:
• L* = {ε, ab, aa, baa, abab, abaa, aabaa, baab, ...}
• L+ = {ab, aa, baa, abab, abaa, aabaa, baab, ...} (Same as L*, but excluding ε)
Q2 (b) - Convert NFA for (a+b) b (a+b) to DFA*
Steps
Difference
1. Construct NFA
• L* includes the empty string ε, whereas L+ does not.
• Start at state A
• Transition on b to B
Q1 (b) - Minimize the Given DFA • Transition from B on a or b to C
• C is the final state
Steps to Minimize a DFA 2. Convert NFA to DFA using subset construction.
1. Identify states and transitions from the given DFA
2. Partition states into two groups: State Transition Table for DFA
• Group 1: Final states {q4, q5} NFA States a b
• Group 2: Non-final states {q0, q1, q2, q3} A A B
3. Check for equivalent states: B C C
• If two states have the same behavior, merge them.
C C C
4. Construct the minimized DFA based on merged states.
Q3 (a) - Grammar Derivation & Ambiguity Check
Minimized DFA Table
Given grammar:
State 0 1
S → 0B | 1A
q0 q1 q2 A → 0S | 1AA
q1 q3 q4 B → 1S | 0BB
q2 q5 q6
For 001101, derivation steps:
q3 q1 q4
q4 q5 q6 1. S → 0B
q5 q3 q4 2. B → 1S
3. S → 1A
Q2 (a) - Construct DFA for Strings Avoiding "00" and "11" 4. A → 0S
5. S → 0B
State Representation 6. B → 1S
• q0: Start state
• q1: Last digit was 0 Parse Tree for 001101
• q2: Last digit was 1 S
• Dead: Trap state (if 00 or 11 appears) / \
0 B
/ \
1 S
/ \ S → aSb | bSa | ε
1 A
/ \
0 S
/ \ Q5 (b) - Prove Regular Expression Equivalence
0 B
/ \ To prove (ab + a) ab = (aa b)**:
1 S
1. Expand both expressions.
Ambiguity: Since multiple parse trees exist for the same string, the grammar is ambiguous. 2. Show that one is a subset of the other.
3. Prove equivalence.
Q3 (b) - Regular Language Properties
Regular languages are closed under:
• Union
• Intersection
• Concatenation
• Kleene Star
• Complement
• Difference
Example Proof
• If L1 and L2 are regular, their intersection L1 ∩ L2 is regular (using DFA intersection).
Q4 (a) - Pumping Lemma Proof for L = {0ⁿ1⁰ | n ≥ 1}
To check if L is regular, we assume it is and use the Pumping Lemma:
1. Assume L is regular.
2. Choose w = 0ⁿ1⁰ where n ≥ p (pumping length).
3. Split w into xyz:
• |xy| ≤ p (contains only 0s)
• y≠ε
• xy²z ∈ L must hold.
4. If y is pumped (y repeated), 0s count changes while 1s remain fixed.
• This violates the structure of L (0ⁿ1⁰ form is broken).
• Contradiction! L is not regular.
Q4 (b) - Convert Mealy Machine to Moore Machine
Steps
1. Convert Mealy's transition-output pairs to state-based outputs.
2. Assign new states.
3. Merge equivalent states.
Q5 (a) - Context-Free Grammar for Equal a’s and b’s
The CFG for equal a and b count:
