Formal Language & Automata Theory

(I) NFA, in its name has 'non-deterministic' because of ____________

Answer: multiple transitions for a single input symbol from a given state (and possible ε-transitions)
Explanation: The automaton can "guess" multiple paths simultaneously, hence it is non-deterministic.

(II) The non-Kleene Star operation accepts the following string of finite length over set A = {0,1} | where string s contains even number of 0 and 1

Answer: Positive Closure (+)
Explanation: The Kleene Star (*) accepts the empty string (ε). The non-Kleene star operation usually refers to the Positive Closure (+), which requires at least one occurrence. For the language of even 0s and 1s, this ensures the accepted strings have a finite length greater than zero.

(III) Language of finite automata is of which type?

Answer: Type 3 (Regular Language)
Explanation: According to the Chomsky hierarchy, finite automata accept Type 3 or Regular languages.

(IV) The concept of FSA is much used in _____________ part of the compiler

Answer: Lexical Analysis
Explanation: Finite State Automata (FSA) are used by the scanner (lexical analyzer) to match regular expressions and generate tokens.

(V) FSM can recognize ___________

Answer: Regular Languages

(VI) Consider the following language, L = {aⁿ bⁿ | n = 1}. L is ____________

Answer: a Regular Language
Explanation: Since n=1, the language is simply L = {ab}. Any finite language is a regular language.

(VII) Set of regular languages over a given alphabet set is closed under ________

Answer: Union, Intersection, Concatenation, Kleene Closure, and Complementation

(VIII) Consider the grammar: S -> aBSc | abc, Ba -> aB, Bb -> bb, Bc -> bc. Write the sentences can be derived by this grammar?

Answer: Sentences of the form aⁿbⁿcⁿ where n ≥ 1. (e.g., abc, aabbcc, aaabbbccc)
Derivation Example (n=2):
S ⇒ aBSc ⇒ aB(abc)c = aBabcc ⇒ aaBbcc ⇒ aabbcc.

(IX) Consider the following grammar: S -> Ax | By, A -> By | Cw, B -> x | Bw, C -> y. Write the regular expressions describe the same set of strings as the grammar.

Answer: xw*yx + ywx + xw*y
Explanation: By solving the left-linear grammar equations:
C = y
B = xw*
A = By | Cw = xw*y | yw
S = Ax | By = (xw*y | yw)x | xw*y = xw*yx | ywx | xw*y

(X) Let S = {a, b, c, d, e}. The number of strings is ___________ in S* of length 4 such that no symbol is used more than once in a string.

Answer: 120
Explanation: Number of ways to arrange 4 unique symbols out of 5 is P(5,4) = 5 × 4 × 3 × 2 = 120.

(XI) Given a grammar G, a production of G with a dot at some position of the right side is called _______

Answer: an LR(0) item

(XII) Number of states of the FSM required to simulate behaviour of a computer with a memory capable of storing "m" words, each of length 'n' is ______

Answer: 2^mn
Explanation: The total number of bits is m × n. Each bit can be in 2 states (0 or 1). Thus, total states = 2^{m × n}.

Solution:
Let L = {w ∈ {0,1}* | w starts with 01 or w ends with 01}.
We can track the prefix and suffix simultaneously. Once a string starts with "01", it enters an accepting sink state. If it does not start with "01", we must track its ending characters to see if it ends with "01".

States:
• q0: Initial state.
• q1: Seen '0' at the very beginning.
• q2: Started with "01". This is an Accepting Sink State.
• q3: Did not start with "01" (e.g. started with 1), currently ending in neither.
• q4: Did not start with "01", currently ending in '0'.
• q5: Did not start with "01", currently ending in "01". Accepting State.

State	0	1
→ q0	q1	q3
q1	q4	*q2
*q2 (Accept)	q2	q2
q3	q4	q3
q4	q4	*q5
*q5 (Accept)	q4	q3

Solution:
The language consists of strings with one or more 'a's. This represents the positive closure of 'a'.
Regular Expression: a⁺ or aa*

Solution:
This regular expression generates all strings over {0,1} that contain the substring "00".

Solution:
This is a standard Deterministic Pushdown Automaton (DPDA) for palindromes with a defined center marker 'c'.
Let PDA P = (Q, Σ, Γ, δ, q₀, Z₀, F)
Where:
Q = {q₀, q₁, q₂}
Σ = {a, b, c}
Γ = {a, b, Z₀}
F = {q₂} (Accepting state)

Transition Functions (δ):

State	Input	Stack Top	Action (Next State, Push/Pop)	Description
q₀	a	Z₀	(q₀, aZ₀)	Push first half (W) onto the stack
q₀	b	Z₀	(q₀, bZ₀)
q₀	a	a	(q₀, aa)
q₀	b	a	(q₀, ba)
q₀	a	b	(q₀, ab)
q₀	b	b	(q₀, bb)
q₀	c	Z₀	(q₁, Z₀)	Center marker 'c' found. Switch to popping state
q₀	c	a	(q₁, a)
q₀	c	b	(q₁, b)
q₁	a	a	(q₁, ε)	Match Wᴿ characters by popping stack
q₁	b	b	(q₁, ε)
q₁	ε	Z₀	(q₂, Z₀)	Stack empty (only Z₀ left), Accept

Given NFA:
States: {q0, q1, q2}, Start: q0, Final: q1.
Transitions identified from diagram:
δ(q0, a) = {q1, q2}, δ(q0, b) = Φ
δ(q1, a) = Φ, δ(q1, b) = {q0}
δ(q2, a) = {q1}, δ(q2, b) = {q1, q2}

Conversion to DFA via Subset Construction:

DFA State	Input 'a'	Input 'b'
→ {q0}	{q1, q2}	Φ
* {q1, q2}	{q1}	{q0, q1, q2}
* {q1}	Φ	{q0}
* {q0, q1, q2}	{q1, q2}	{q0, q1, q2}
Φ (Dead State)	Φ	Φ

Note: Any DFA state containing the NFA's final state 'q1' becomes an accepting state (marked with *).

Solution:
We need a DFA to accept the language L = {w ∈ {0,1}* | w ends in 001}.

States:
• q0: Start state. (Seen nothing or sequence broken)
• q1: Seen "0"
• q2: Seen "00"
• q3: Seen "001" (Accepting State)

Based on the given DFA diagram:
q1 (start): loop on 1, arrow to q2 on 0
q2: loop on 0, arrow to q3 on 1
q3 (final): loop on 0, long arrow back to q1 on 1

Formulating state equations (Arden's Theorem):
Q1 = ε + Q1·1 + Q3·1
Q2 = Q1·0 + Q2·0
Q3 = Q2·1 + Q3·0

Solving equations:
From Q2: Q2(1 - 0) = Q1·0 ⇒ Q2 = Q1·00*
From Q3: Q3(1 - 0) = Q2·1 ⇒ Q3 = Q2·10* = Q1·00*10*

Substitute Q3 into Q1 equation:
Q1 = ε + Q1·1 + Q1·00*10*1
Q1(1 - 1 - 00*10*1) = ε
Q1 = (1 + 00*10*1)*

Since Q3 is the only final state, the Regular Expression is Q3:
Q3 = Q1·00*10* = (1 + 00*10*1)* 00*10*

Given e-NFA Table:

State	ε	a	b
→ p	{r}	{q}	{p, r}
q	Φ	{p}	Φ
* r	{p, q}	{r}	{p}

Step 1: Compute ε-closures
• ε-closure(p): Starts with {p}. p-ε→r (Add r). r-ε→p,q (Add q). Result = {p, q, r}.
• ε-closure(q): Starts with {q}. q-ε→Φ. Result = {q}.
• ε-closure(r): Starts with {r}. r-ε→p,q (Add p,q). Result = {p, q, r}.

Step 2: Convert to DFA
Start state of DFA is A = ε-closure(start_state) = ε-closure(p) = {p, q, r}.
Since 'r' is a final state in the NFA, any DFA state containing 'r' is final. Thus, A is a Final State.

Compute transitions for State A = {p, q, r}:
• On input 'a':
δ_NFA({p,q,r}, a) = δ(p,a) ∪ δ(q,a) ∪ δ(r,a) = {q} ∪ {p} ∪ {r} = {p, q, r}.
DFA Transition = ε-closure({p, q, r}) = {p, q, r} = A.

• On input 'b':
δ_NFA({p,q,r}, b) = δ(p,b) ∪ δ(q,b) ∪ δ(r,b) = {p, r} ∪ Φ ∪ {p} = {p, r}.
DFA Transition = ε-closure({p, r}) = ε-closure(p) ∪ ε-closure(r) = {p, q, r} = A.

Resulting DFA:
The equivalent DFA is a single state `{p, q, r}` which is both the initial and final state. It loops to itself on inputs 'a' and 'b'. The language accepted is (a+b)*.

Definition:
A Context-Free Grammar (CFG) is in Chomsky Normal Form (CNF) if every production rule is of the form:
1. A → BC (where B and C are non-terminal variables)
2. A → a (where a is a terminal symbol)
Exceptions: S → ε is permitted if the start symbol S does not appear on the right side of any rule.

Conversion to CNF:
Given Grammar:
S → aSb | ab | Aa
A → aab

Step 1: Eliminate ε, unit, and useless productions. (None exist here).

Step 2: Replace terminals in mixed bodies with new variables.
Let Xₐ → a, X_b → b.
S → Xₐ S X_b | Xₐ X_b | A Xₐ
A → Xₐ Xₐ X_b

Step 3: Restrict the number of variables on the right side to exactly two.
Introduce new variables S₁ and A₁ to break down long sequences:
S → Xₐ S₁ | Xₐ X_b | A Xₐ
S₁ → S X_b
A → Xₐ A₁
A₁ → Xₐ X_b
Xₐ → a
X_b → b

This is the final CFG in Chomsky Normal Form.

Definition:
A production is useless if the variable involved cannot be reached from the start symbol, or if it cannot generate a string of purely terminal symbols.

Step 1: Eliminate ε-productions
Nullable variable: D (since D → ε).
Update rules where D is present:
Since B → D, B is also nullable.
Since C → B, C is also nullable.
Update grammar by resolving these:
D → a
B → aba | b | D
A → bA | Bba | aa | ba (added 'ba' due to 'Bba' where B is nullable)
C → CA | AC | B | A (added A due to nullable C)

Step 2: Eliminate Unit productions
Unit pairs are (B, D), (C, B), (C, A).
Expand D into B: B → aba | b | a
Expand B into C: C → CA | AC | A | aba | b | a
Expand A into C: C → CA | AC | bA | Bba | aa | ba | aba | b | a
Grammar after Unit Removal:
A → bA | Bba | aa | ba
B → aba | b | a
C → CA | AC | bA | Bba | aa | ba | aba | b | a
D → a

Step 3: Eliminate Useless productions
1. Generating test: All variables (A, B, C, D) can generate strings of terminals. No variables are eliminated here.
2. Reachable test: The start symbol is 'A'.
From A, we can reach 'A' (A → bA) and 'B' (A → Bba).
However, variables C and D are never reached from A! Thus, C and D, along with all their productions, are useless and must be removed.

Final Simplified Grammar:
A → bA | Bba | aa | ba
B → aba | b | a

Non-Deterministic PDA (NPDA):
An NPDA is defined as a 7-tuple (Q, Σ, Γ, δ, q₀, Z₀, F) where:
• Q is a finite set of states.
• Σ is a finite input alphabet.
• Γ is a finite stack alphabet.
• δ is the transition function mapping Q × (Σ ∪ {ε}) × Γ to finite subsets of Q × Γ*.
• q₀ is the start state.
• Z₀ is the initial stack symbol.
• F is the set of accepting/final states.
In NPDA, for a given state, input, and stack top, there can be multiple possible transitions (it "guesses").

Deterministic PDA (DPDA):
A DPDA is a subclass of PDA that strictly restricts non-determinism. It follows the same 7-tuple definition, but its transition function δ satisfies the following constraints:
1. For any q ∈ Q, a ∈ Σ ∪ {ε}, and X ∈ Γ, the set δ(q, a, X) has at most one element. (|δ(q, a, X)| ≤ 1).
2. For any q ∈ Q and X ∈ Γ, if δ(q, ε, X) is not empty, then δ(q, a, X) must be empty for every a ∈ Σ. (If an ε-transition is possible, no input-consuming transition is allowed simultaneously).

Solution:
We construct the PDA using the standard top-down parser method.
Let PDA P = ({q}, Σ, V, δ, q, S), where Σ = {a, b} and V = {S, A, a, b}.

Transition Functions:
Rule 1: For each production Variable → Body, add a transition that replaces the Variable on the stack with the Body without consuming input.
• δ(q, ε, S) = {(q, aAA)}
• δ(q, ε, A) = {(q, aS), (q, bS), (q, a)}

Rule 2: For each terminal 't' in Σ, add a transition that pops 't' from the stack if it matches the current input symbol.
• δ(q, a, a) = {(q, ε)}
• δ(q, b, b) = {(q, ε)}

This single-state PDA accepts strings generated by the CFG using empty stack acceptance.

(a) State the Pumping lemma for the Regular Language (RL) [4]
If L is a regular language, then there exists a constant 'p' (the pumping length) such that any string 'w' in L with length |w| ≥ p can be split into three parts, w = xyz, satisfying the following three conditions:
1. |y| > 0 (The middle part is non-empty)
2. |xy| ≤ p (The first two parts are at most length p)
3. For all i ≥ 0, the string xyⁱz is also in L.

(b) State the Pumping lemma for the Context Free Language (CFL) [4]
If L is a context-free language, then there exists a constant 'p' (the pumping length) such that any string 'w' in L with length |w| ≥ p can be split into five parts, w = uvxyz, satisfying the following three conditions:
1. |vx| > 0 (Either v or x is non-empty)
2. |vxy| ≤ p (The middle three parts are at most length p)
3. For all i ≥ 0, the string uvⁱxyⁱz is also in L.

(c) Prove that the given language is not regular. L = {aⁿ bⁿ | n ≥ 0} [7]
Proof by Contradiction:
1. Assume L is a regular language. Therefore, the Pumping Lemma for regular languages must apply.
2. Let 'p' be the pumping length specified by the lemma.
3. We choose a specific string w ∈ L such that w = aᵖbᵖ. Clearly, |w| = 2p ≥ p, so it meets the length requirement.
4. According to the lemma, w can be divided into w = xyz, where |xy| ≤ p and |y| > 0.
5. Since |xy| ≤ p and the string w begins with 'p' consecutive 'a's, the substrings 'x' and 'y' must consist entirely of 'a's. Therefore, y = aᵏ for some k > 0.
6. By the pumping lemma, pumping 'y' by setting i = 2 (xy²z) must result in a string that is also in L.
7. When we pump the string (i=2), we add 'k' more 'a's. The new string becomes aᵖ⁺ᵏbᵖ.
8. Since k > 0, p+k ≠ p. The new string has more 'a's than 'b's, which means it is NOT in the language L (L requires equal numbers of 'a's and 'b's).
9. This violates the Pumping Lemma, contradicting our initial assumption. Thus, L is not a regular language. (Proved)

Definition:
Greibach Normal Form (GNF) requires all productions to be in the form A → aα, where 'a' is a terminal and 'α' is a string of zero or more variables.

Step 1: Convert to Aᵢ → Aⱼ γ format where j > i
Given rules:
A₁ → A₂ A₃ (Valid, 1 < 2)
A₂ → A₃ A₁ | b (Valid, 2 < 3)
A₃ → A₁ A₂ | a (Invalid, 3 > 1)

Substitute A₁ into A₃'s invalid rule:
A₃ → (A₂ A₃) A₂ | a ⇒ A₃ → A₂ A₃ A₂ | a
Now we have A₃ → A₂... (Invalid, 3 > 2).

Substitute A₂ into A₃:
A₃ → (A₃ A₁ | b) A₃ A₂ | a
A₃ → A₃ A₁ A₃ A₂ | b A₃ A₂ | a

Step 2: Eliminate Left Recursion in A₃
A₃ has immediate left recursion: A₃ → A₃ A₁ A₃ A₂.
Let α = A₁ A₃ A₂. Let β = b A₃ A₂ and β₂ = a.
Using the standard formula for left recursion elimination (A → β | βZ, Z → α | αZ):
A₃ → b A₃ A₂ | a | b A₃ A₂ Z | a Z
Z → A₁ A₃ A₂ | A₁ A₃ A₂ Z

Now, all A₃ rules begin with terminal symbols!

Step 3: Back-substitute to make all other variables start with terminals
Substitute A₃ into A₂ (A₂ → A₃ A₁ | b):
A₂ → (b A₃ A₂ | a | b A₃ A₂ Z | a Z) A₁ | b
A₂ → b A₃ A₂ A₁ | a A₁ | b A₃ A₂ Z A₁ | a Z A₁ | b
Now, all A₂ rules begin with terminal symbols!

Substitute A₂ into A₁ (A₁ → A₂ A₃):
A₁ → (b A₃ A₂ A₁ | a A₁ | b A₃ A₂ Z A₁ | a Z A₁ | b) A₃
A₁ → b A₃ A₂ A₁ A₃ | a A₁ A₃ | b A₃ A₂ Z A₁ A₃ | a Z A₁ A₃ | b A₃
Now, all A₁ rules begin with terminal symbols!

Step 4: Substitute A₁ into Z
Z → A₁ A₃ A₂ | A₁ A₃ A₂ Z
Substitute the long set of A₁ rules into Z. Since A₁ has 5 rules, this will create 10 rules for Z, all starting with terminals.

Final Grammar in GNF:

A₁ → bA₃A₂A₁A₃ | aA₁A₃ | bA₃A₂ZA₁A₃ | aZA₁A₃ | bA₃

A₂ → bA₃A₂A₁ | aA₁ | bA₃A₂ZA₁ | aZA₁ | b

A₃ → bA₃A₂ | a | bA₃A₂Z | aZ

Z → bA₃A₂A₁A₃A₃A₂ | aA₁A₃A₃A₂ | bA₃A₂ZA₁A₃A₃A₂ | aZA₁A₃A₃A₂ | bA₃A₃A₂ |
    bA₃A₂A₁A₃A₃A₂Z | aA₁A₃A₃A₂Z | bA₃A₂ZA₁A₃A₃A₂Z | aZA₁A₃A₃A₂Z | bA₃A₃A₂Z