1⃣ prove the pumping lemma

• (Assume)L is a regular language.

• Then, there exists a DFA M = (Q, Σ, δ, q₀, F) that accepts L.
• Let p = |Q| = number of states in M.
Now take any string s ∈ L such that |s| ≥ p.
Since the string has at least p symbols and only p states in DFA, some state
must repeat during the computation.
Let’s say the repeated path is:
s = x y z
↑
loop (repeats y)
Where:
• x: leads from the start to the rst occurrence of a repeated state.
• y: the loop that causes repetition.
• z: the remaining part after the loop.
This gives:
• |y| > 0 (because the loop has at least one transition),
• |xy| ≤ p (because the loop occurs within the rst p symbols),
• For any i ≥ 0, xyⁱz ∈ L (looping y doesn’t break the DFA, it remains in
valid transitions).
Thus, the lemma is proved.
Using Pumping Lemma to Prove a Language is NOT Regular
We use proof by contradiction:
Example:
Let L = { aⁿbⁿ | n ≥ 0 }
Assume: L is regular.
Then, by Pumping Lemma, there exists a p such that all strings s ∈ L with |s| ≥
p can be written as s = xyz, satisfying:
• |y| > 0
• |xy| ≤ p
• For all i ≥ 0, xyⁱz ∈ L
Now choose a string s = aᵖbᵖ ∈ L.
Then |s| = 2p ≥ p ✅
According to the lemma, s = xyz with:
• x = a^k
• y = a^l (since |xy| ≤ p, y contains only a's)
• z = a^(p-k-l) b^p
Now, pump y with i = 2:
xy²z = a^k a^2l a^(p−k−l) b^p = a^(p + l) b^p
This means more a's than b's ⇒ Not in L
Contradiction!
So, L is not regular.

2⃣ Prove that L = { aᵖ | p is prime } is not a regular language

Step 1: Assume L is regular

Page 1
fi
fi
Then by the Pumping Lemma, there exists a pumping length p, such that any
string s ∈ L with |s| ≥ p can be split into parts:
s = xyz,
satisfying:
1. |y| > 0
2. |xy| ≤ p
3. For all i ≥ 0, xyⁱz ∈ L
Step 2: Choose a string s in L
Let’s pick a prime number q ≥ p, so that s = a^q ∈ L and |s| ≥ p.
So:
• x = aᵏ
• y = aˡ (l > 0)
• z = a^(q−k−l)
→ s = xyz = aᵏaˡa^(q−k−l) = a^q ✅
Step 3: Pump y (choose i = 2)
Now we consider:
xy²z = xyyz = aᵏa²ˡa^(q−k−l) = a^(q + l)
This means we added l > 0 a's to the string.
Step 4: Contradiction
• q is prime, but q + l may not be prime (and usually isn’t).
• For example: if q = 7 (prime), l = 2 ⇒ q + l = 9 (not prime)
• So xy²z ∉ L
This contradicts the Pumping Lemma❌

3⃣ . Ardens theorem. (R = Q + RP, R = QP*)

Let P and Q be regular expressions over an alphabet Σ.
The equation:
R = Q + RP
(has a regular expression on both sides)
Then the unique solution is:
R = QP*
provided that ε ∉ P (i.e., P does not contain the empty string).
If R = Q + RP, then the smallest solution is R = QP*, assuming ε ∉ P.

1. Show that QP* is a solution**

Let R = QP*.
We check if:
R = Q + RP
= Q + QP*P
Now:
• RP = (QP*)P = Q(P*P)
• Since PP = P (closure property of Kleene star),
• So RP = QP*
Page 2
 Thus: Q + RP = Q + QP* = QP* = R ✅
So QP* satis es the equation.

2. Show it’s the smallest solution

Suppose there's another solution R' such that:
R' = Q + R'P
Let’s prove that R' ⊇ QP* (i.e., R' contains at least all strings in QP*)
We can expand R':
R' = Q + R'P
= Q + (Q + R'P)P
= Q + QP + R'PP
= Q + QP + QPP + QPPP + ...
= Q + QP + QP² + QP³ + ...
= QP*
This shows QP* is the least solution (smallest language) satisfying the equation.
Condition: ε ∉ P is necessary
If ε ∈ P, then *P = P+ ∪ {ε}**, and the closure may loop in nitely without
consuming input — leading to multiple solutions, and the uniqueness breaks.
So we must require ε ∉ P.
Example Use
Say you have:
R = a + Rb
Then by Arden’s Theorem:
R = a(b)*

4⃣ Moore to Mealy Conversion & Proof

Moore Machine:
A Moore machine is a 6-tuple:
M = (Q, Σ, Δ, δ, λ, q₀)
• Q = set of states
• Σ = input alphabet
• Δ = output alphabet
• δ: Q × Σ → Q (transition function)
• λ: Q → Δ (output depends only on state)
• q₀ = start state
🎯 Goal: Construct a Mealy machine M' such that for any input string, M and
M' produce the same output.
🔧 Construction:
De ne Mealy machine:
M = (Q, Σ, Δ, δ, λ , q₀)
Where:
• λ (q, a) = λ(δ(q, a))
→ i.e., the output is the output of the next state in the Moore
machine.
Page 3
′
′
fi
fi
′
fi
 ✅ Why it works:
In Moore, output is produced after entering a state.
In Mealy, we simulate that by labeling the input transition with the output of the
destination state, so the output is seen during the transition.
Thus, for every input symbol, Mealy and Moore produce the same output.
✅ Hence, Moore ⇒ Mealy is proven.

5⃣ Mealy to Moore Conversion & Proof

Mealy Machine:
A Mealy machine is a 6-tuple:
M = (Q, Σ, Δ, δ, λ, q₀)
• λ: Q × Σ → Δ (output depends on state and input)
🎯 Goal: Construct a Moore machine M that produces the same output string
for the same input string (with at most a 1-symbol delay).
🔧 Construction:
We de ne new states in the Moore machine based on both:
• the original state, and
• the output produced on input
So:
States of M = {(q, a) | q ∈ Q, a ∈ Δ}
• λ ((q, a)) = a
• δ ((q, a), x) = (δ(q, x), λ(δ(q, x), x))
→ this gives the next state and its associated output
• Initial state = (q₀, λ(q₀, x₀)) where x₀ is a dummy input (or de ne an
initial output separately)

6⃣ Can two grammars of different types generate the same language?

Yes, two grammars of different types can generate the same language.
For example:
• A regular grammar (Type 3) and a context-free grammar (Type 2)
can both generate the regular language L = { aⁿ | n ≥ 0 }.
• In fact, Type 3 ⊆ Type 2 ⊆ Type 1 ⊆ Type 0, meaning higher-type
grammars can always generate the languages of lower types.
• However, the reverse is not true — a Type 3 grammar cannot
generate a Type 2-only language like L = { aⁿbⁿ | n ≥ 0 }.
•
7⃣ Is the language {aⁿbⁿ | n ≥ 1} accepted by pda by nal state and empty store ?
Yes, A PDA can accept this by:
• Pushing each a onto the stack.
• Then popping one a for each b.
Page 4
′
′
fi
′
′
fi
fi
 •If all as are matched by bs and we reach the nal state, the input is
accepted.
2. Empty Stack (Empty Store) Acceptance?
Yes
Same idea:
• Push a symbols on stack while reading as.
• Pop one a for each b.
• If stack is empty exactly when input ends, accept by empty stack.
Conclusion:
Yes, the language L = { aⁿbⁿ | n ≥ 1 } is accepted by PDA using both nal state
and empty stack methods.

8⃣ De ne analytically/mathematically the sets T(A) and N(A) for a

pusdown automata A.
A = (Q, Σ, Γ, δ, q₀, Z₀, F) where Q = set of states, Σ = input alphabet, Γ =
stack alphabet, δ = transition function, q₀ = start state, Z₀ = initial stack
symbol, F = set of nal states.]

1. T(A): The set of terminal (or accepted) con gurations

De nition:
T(A) is the set of all con gurations from which the PDA accepts the input
(either by nal state or empty stack).
So, formally:
• By nal state acceptance:
T(A) = { (q, w, α) ∈ Q × Σ* × Γ* | (q, w, α) ⊢* (q_f, ε, γ), q_f ∈ F, γ ∈
Γ* }
• By empty stack acceptance:
T(A) = { (q, w, α) ∈ Q × Σ* × Γ* | (q, w, α) ⊢* (q', ε, ε) for some q' ∈
Q}
(Here, ⊢* means “zero or more steps in the transition relation.”)

2. N(A): The set of non-terminal (or non-accepting) con gurations

De nition:
N(A) = (Q × Σ* × Γ*) − T(A)
That is, all con gurations that do not lead to acceptance by the PDA.

9⃣ If Σ (sigma) is nite, then Σ⁺ is nite.

FALSE
• Σ = input alphabet (a nite set). Example: Σ = {a, b}
• Σ⁺ = set of all non-empty strings over Σ
= {a, b, aa, ab, ba, bb, aaa, …}
= in nite set
Page 5
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
 Why?
Because for any positive length n, there are |Σ|ⁿ strings of length n, and n can
be any natural number ≥ 1. So:
Σ⁺ = ⋃_{n=1}^∞ Σⁿ → in nite union of nite sets = in nite

1⃣ 0⃣ Using Pumping lemma prove that the language {1^P/p

is prime} is not a context free language
Given:
Let L = { 1ᵖ | p is a prime number }
We will prove that L is not a context-free language using the Pumping Lemma
for CFLs.
🔷 Step 1: Assume L is context-free.
Then, by the pumping lemma for CFLs, there exists a pumping length p such
that any string s ∈ L, with |s| ≥ p, can be written as:
s = uvwxy, satisfying:
1. |vwx| ≤ p
2. vx ≠ ε
3. For all i ≥ 0, u(v)ⁱw(x)ⁱy ∈ L
🔷 Step 2: Choose a speci c string
Choose s = 1ᵖ, where p is a prime number such that p > pumping length.
So, s ∈ L and |s| ≥ p.
🔷 Step 3: Apply the lemma
Since s = 1ᵖ, it's a string of only 1’s.
So:
• s = uvwxy
• The substrings v and x consist only of 1’s, and vx ≠ ε
Let |vx| = k ≥ 1
Then, for i = 2, the pumped string becomes:
s' = uv²wx²y
So length of s' = p + k
🔷 Step 4: Show contradiction
• After pumping, length = p + k
• But p + k is not necessarily a prime number (e.g., prime + 1, prime + 2,
etc.)
• So s ∉ L
Hence, pumping lemma fails ⇒ Contradiction.
🔷 Final Conclusion:
So, our assumption is wrong.
∴ L = {1ᵖ | p is prime} is NOT a context-free language.

1⃣ 1⃣ Construct a nite automata without empty moves which is

equivalent to the regular expression: (0 + 1)* (00 + 11)(0 + 1)*
To construct a nite automaton without ε-moves equivalent to the regular
expression:
Page 6
′
fi
fi
fi
fi
fi
fi
 R = (0 + 1)* (00 + 11)(0 + 1)*
Let’s break this down and follow clear steps to get a DFA/NFA for it.
Language Description:
This regular expression represents:
All strings over {0, 1} that contain either "00" or "11" as a substring.
So we are building a machine that accepts all binary strings that contain either
"00" or "11" somewhere in the middle.
Step-by-step Construction
We’ll construct a DFA directly, without ε-moves.
Goal: Accept strings containing either "00" or "11".
States:
We’ll de ne a DFA with states that track the possibility of seeing 00 or 11.
Let’s de ne the states:
Stat Meaning Fro Input To Comment
e m
q0 Start state (no pattern seen yet) q0 0 q1 Start 0 seen
q1 Last symbol was 0 q0 1 q2 Start 1 seen
q2 Last symbol was 1 q1 0 q3 "00" detected
q3 "00" seen — accept state q1 1 q2 Switch to 1
q4 "11" seen — accept state q2 0 q1 Switch to 0
q2 1 q4 "11" detected
q3 0 q3 Stay in accept
Transitions: ➡ q3 1 q3 Stay in accept
q4 0 q4 Stay in accept
q4 1 q4 Stay in accept

Final Automaton:
• States: {q0, q1, q2, q3, q4}
• Alphabet: {0, 1}
• Start state: q0
• Accept states: {q3, q4}
• No ε-moves
This DFA accepts all strings that contain "00" or "11" — exactly what the
regular expression (0 + 1)*(00 + 11)(0 + 1)* denotes.
0 0
+------> q1 ---> q3 (accept)
| | ↑
| |1 |0,1
| v |
q0 ---> q2 --->+
| |
| |1
+——-+
1
q2 --1--> q4 (accept)
q3 and q4 loop on 0,1 to themselves
Page 7
fi
fi
1⃣ 2⃣ Reduce the following grammar to Chomsky Normal Form.
S→ ASA | bA, A →B|S, B→c
Step 1: Eliminate terminals from right-hand sides longer than 1
In CNF, each production must be either:
• A → BC (two non-terminals)
• A → a (single terminal)
Let's start by replacing terminals that appear alongside non-terminals.
Identify terminals in rules with length > 1:
• S → ASA is ne (all non-terminals)
• S → bA contains terminal b + non-terminal A
• B → c is terminal alone → okay.
We need to replace b with a non-terminal.
Introduce new non-terminal for terminal b:
Let
X_b → b
Rewrite:
S → X_b A
Step 2: Replace all productions with RHS length > 2
• S → A S A (length 3)
Break into binary productions:
Create a new non-terminal Y:
• S → A Y
• Y → S A
Step 3: Write updated grammar
less
S → A Y | X_b A
Y → S A
A → B | S
B → c
X_b → b
Step 4: Check for unit productions (productions of the form A → B)
Currently, unit productions:
• A → B
• A → S
CNF does not allow unit productions; we must eliminate them.

Step 5: Eliminate unit productions

• For A → B: Replace with B → c, so add A → c
• For A → S: Replace with productions of S:
S → A Y | X_b A
So add to A:
A → A Y | X_b A
Now, remove unit productions A → B and A → S.
Updated grammar:
Page 8
fi
S → A Y | X_b A
Y → S A
A → c | A Y | X_b A
B → c
X_b → b
Step 6: Check again for any unit productions
No more unit productions remain.
Step 7: Final check for CNF:
• All productions are either:
◦ A → BC (two non-terminals), e.g. S → A Y, Y → S A, A → A
Y, A → X_b A
◦ A → a (single terminal), e.g. A → c, X_b → b
So grammar is now in Chomsky Normal Form.
Final CNF Grammar:
S → A Y | X_b A
Y → S A
A → c | A Y | X_b A
B → c
X_b → b

1⃣ 3⃣ Convert the following grammar S→asb|A, A →bSa|S|A to a pushdown

automata that accepts same language: A. by empty stack B. by nal state.

We will convert this grammar into two PDAs:

1. PDA that accepts by empty stack
2. PDA that accepts by nal state

✅ GENERAL STRATEGY (CFG → PDA)

To convert a CFG to a PDA that accepts by empty stack, we use this general
idea:
1. PDA simulates leftmost derivations
2. Initially pushes the start symbol onto the stack
3. Repeatedly:
◦ Replaces non-terminals with RHS of productions
◦ Matches terminals with input
💡 Let’s denote the PDA as:
M = (Q, Σ, Γ, δ, q₀, Z₀, F)
Where:
• Q = {q₀} (just one state for now)
• Σ = {a, b}
• Γ = {S, A, a, b, Z₀}
Page 9
fi
fi
 • q₀ = start state
• Z₀ = initial stack symbol
• F = ∅ (for empty-stack acceptance) or {q₀} (for nal-state acceptance)
(A) PDA Accepting by Empty Stack
We’ll design M₁ that simulates the grammar.

Step 1: Initialization
Push the start symbol S on the stack.
• δ(q₀, ε, Z₀) = (q₀, SZ₀)
Step 2: Replace Non-terminals (Simulate production rules)
• For S → asb
δ(q₀, ε, S) = (q₀, b s a)
Push in reverse: RHS = asb → push b, then s, then a
• For S → A
δ(q₀, ε, S) = (q₀, A)
• For A → bSa
δ(q₀, ε, A) = (q₀, a S b)
• For A → S
δ(q₀, ε, A) = (q₀, S)
• For A → A
δ(q₀, ε, A) = (q₀, A)
(optional, means A → A, can be removed)
Step 3: Match terminals
• δ(q₀, a, a) = (q₀, ε)
• δ(q₀, b, b) = (q₀, ε)
PDA Accepts by Empty Stack
M₁ = (Q = {q₀}, Σ = {a, b}, Γ = {a, b, S, A, Z₀}, δ, q₀, Z₀, ∅)
(B) PDA Accepting by Final State
We convert PDA to accept by nal state. This means:
• Add a new nal state qf
• When stack becomes empty, move to qf
Add transition:
• δ(q₀, ε, Z₀) = (qf, Z₀)
(i.e., when Z₀ is on stack and input is done, go to nal state)
Final PDA (M₂):
• Same as M₁, but with F = {qf}
• Add nal state qf
• Add ε-transition from q₀ to qf when stack has only Z₀ (or is empty)
Summary:
PDA Accepting by Empty Stack:
• Simulates grammar by pushing start symbol
• Replaces non-terminals
• Matches terminals
Page 10
fi
fi
fi
fi
fi
 • Accepts when stack is empty

1⃣ 4⃣ Find the reduce grammar equivalent to the grammar S-aAa,

A-bBB, B→ ab, C→aB
Step 1: Identify generating symbols
(A symbol is generating if it can eventually produce a string of terminals.)
Start from terminals and work backward.
B → ab
• ab ∈ Σ* → B is generating
A→bBB
• B is generating, and b is a terminal → A is generating
S→aAa
• A is generating → S is generating
C→aB
• a is terminal, B is generating → C is generating, BUT C is not reachable (see next step)

✅ Step 2: Identify reachable symbols

(A symbol is reachable if it can be derived starting from the start symbol S.)
Start from S:
• S → a A a → A is reachable
• A → b B B → B is reachable
C is not reachable (nowhere used or derivable from S)

✅ Step 3: Remove unreachable or non-generating symbols

From above:
• All of S, A, B are reachable and generating
• C is unreachable → remove its rule

✅ Final Reduced Grammar:

S → a A a
A → b B B
B → ab

1⃣ 5⃣ Prove/Disprove that each of the classes of languages in Chomsky

Classi cation (Type 0, Type 1, Type 2 and Type 3) is closed under
concatenation.
Chomsky Language Classes:
Type Name Grammar Type Recognizer
0 Recursively Unrestricted Grammar Turing Machine
Enumerable
1 Context-Sensitive Context-Sensitive Grammar Linear Bounded
Automaton
2 Context-Free Context-Free Grammar Pushdown Automaton
3 Regular Regular Grammar Finite Automaton

Closure Under Concatenation:

We now check whether each class is closed under concatenation — i.e., if
L1,L2 are in the class, then is L1L2={xy∣x∈L1,y∈L2}L1 L2
={xy∣x∈L1 ,y∈L2 } also in the class

Page 11
fi
🔹 Type 3: Regular Languages
Closed under concatenation
Reason:
• Regular languages are closed under concatenation.
• If you have two DFAs/NFAs for L₁ and L₂, you can build an NFA for L1
L2 by connecting nal states of the rst to the start of the second using ε-
transitions.

🔹 Type 2: Context-Free Languages (CFLs)

Closed under concatenation
Reason:
• Let G₁ and G₂ be CFGs for L₁ and L₂.
• You can construct a new CFG that derives strings of L₁L₂ using a new
start symbol:
S→S1 S2 where S1 and S2 are start symbols of G₁ and G₂.
Note: CFLs are not closed under intersection, but they are closed under
concatenation.

🔹 Type 1: Context-Sensitive Languages (CSLs)

Closed under concatenation
Reason:
• The class of context-sensitive languages is closed under concatenation.
• You can simulate derivations of L₁ and L₂ sequentially using a linear
bounded automaton (LBA).

🔹 Type 0: Recursively Enumerable Languages (RELs)

Closed under concatenation
Reason:
• Turing Machines can run a TM for L₁ on part of the string, then a TM for
L₂ on the remaining part.
• Thus, recursively enumerable languages are closed under concatenation.

Page 12
fi
fi