FLAT Previous Year Questions

(i) NFA, in its name has 'non-deterministic' because of ________

Answer: Multiple possible transitions for a single input symbol from a given state (and/or epsilon transitions).
Explanation: In an NFA, for a specific state and input symbol, the automaton can transition to zero, one, or multiple next states, making its path 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 (*) includes the empty string (ε). The Positive Closure (+) operation generates all possible strings of finite length strictly excluding the empty string (unless explicitly added). It acts as the "non-empty" counterpart to the Kleene Star.

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

Answer: Type-3 (Regular Language)
Explanation: According to the Chomsky Hierarchy, finite automata recognize Regular Languages, which are designated as Type-3 languages.

(iv) The concept of FSA is much used in ___________ part of the compiler

Answer: Lexical Analysis
Explanation: Finite State Automata (FSA) and Regular Expressions are used by lexical analyzers (like Lex) to scan source code and group characters into meaningful tokens.

(v) FSM can recognize ___________

Answer: Regular Languages

(vi) Consider the following language, L = {aⁿbⁿ | n ≥ 1}. L is ________

Answer: Context-Free Language (CFL) / Non-Regular Language
Explanation: Finite automata cannot count arbitrarily large values, so L cannot be regular. It requires a stack to match the count of 'a's with 'b's, making it a Context-Free Language recognized by a Pushdown Automaton.

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

Answer: Union, Intersection, Complementation, Concatenation, and Kleene Star.

(viii) Consider the grammar: S → ABcc | Abc, BA → AB, Bb → bb, Ab → ab, Aa → aa. Write the sentences can be derived by this grammar?

Answer: "abc"
Explanation: Using the production S → Abc, we can apply Ab → ab to get "abc". If we attempt S → ABcc, we get stuck because the grammar has no rules to reduce 'Bc' or 'B' when followed by 'c' without a leading terminal. This grammar structurally resembles context-sensitive rules but is missing necessary productions for longer terminal strings.

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

Answer: xw*yx + ywx + xw*y
Explanation: Using Arden's Theorem (R = Q + RP ⇒ R = QP*):
C = y
B = x + Bw ⇒ B = xw*
A = By + Cw = By + yw
S = Ax + By = (By + yw)x + By = Byx + ywx + By
Substitute B = xw*:
S = (xw*)yx + ywx + (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: We are forming permutations of 4 distinct symbols chosen from a set of 5. This 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: LR(0) Item (or simply Item)
Explanation: An item represents how much of a production has been seen so far during bottom-up parsing.

(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 memory has a total capacity of m × n bits. Since each bit can exist in 2 states (0 or 1), the total number of possible combinations (states) is 2^mn.

To design this DFA efficiently, we recognize two parallel conditions. We can build a unified minimal DFA with 6 states.
States Definition:

• q0 (Start): Initial state.
• q1: Saw '0' at the very beginning.
• q2 (Final): Saw '01' at the very beginning. It traps everything and accepts since the prefix condition is met.
• q_wait: Failed the "starts with 01" condition, currently tracking for "ends with 01".
• q_wait0: Tracking for "ends with 01" and just saw a '0'.
• q_wait01 (Final): Failed prefix condition, but just completed the suffix '01'.

Transition Table:

Regular Expression:

a⁺   or   aa^*

Explanation: The language requires at least one occurrence of the symbol 'a' since n > 0. The Kleene Plus operator (+) specifies 1 or more occurrences. Alternatively, it can be written as a single 'a' concatenated with a Kleene Star (0 or more occurrences of 'a').

The language consists of all strings over {0,1} that contain the substring "00".
States:

• q0 (Start): Loops on {0,1} non-deterministically, waits for the first '0' of the substring.
• q1: Has seen the first '0', expects the second '0'.
• q2 (Final): Has seen the "00" substring, accepts and loops on {0,1} forever.

Transition Table for NFA:

This language represents palindromes with a designated center marker 'c'. W^R is the reverse of W.
The PDA works by pushing the first half (W) onto the stack. Upon seeing the center marker 'c', it switches states and begins popping characters from the stack, ensuring they match the input characters of the second half (W^R).

PDA Formal Definition: M = (Q, Σ, Γ, δ, q0, Z0, F)
Q = {q0, q1, qf}, Σ = {a, b, c}, Γ = {a, b, Z0}, F = {qf}

Transition Functions (δ):

Given NFA:
→ q0 →(ε)→ q1,   q0 →(a)→ q2
q1 →(a,b)→ q2
q2 →(b)→ q2
Final State: *q1

Step 1: Compute ε-closures for all states:
ε-closure(q0) = {q0, q1} (since q0 transitions to q1 on ε)
ε-closure(q1) = {q1}
ε-closure(q2) = {q2}

Step 2: Construct DFA States and Transitions:
Start State A = ε-closure(q0) = {q0, q1}. Since q1 is a final state in the NFA, A is a Final State.

Transitions from A {q0, q1}:
- On 'a': ε-closure( δ(q0,a) ∪ δ(q1,a) ) = ε-closure({q2} ∪ {q2}) = {q2}. Let this be state B.
- On 'b': ε-closure( δ(q0,b) ∪ δ(q1,b) ) = ε-closure(φ ∪ {q2}) = {q2} = state B.

Transitions from B {q2}:
- On 'a': ε-closure( δ(q2,a) ) = ε-closure(φ) = φ. Let this be dead state C.
- On 'b': ε-closure( δ(q2,b) ) = ε-closure({q2}) = {q2} = state B.

Transitions from C (φ):
- On 'a', 'b': Goes to C.

Resulting DFA Transition Table:

States:

• q0 (Start): Initial state, hasn't seen any relevant prefix of "001".
• q1: Has seen "0".
• q2: Has seen "00".
• q3 (Final): Has seen the complete suffix "001".

Given DFA Transitions:
Start state is q1. Final state is q2.
q1 →(1)→ q1,   q1 →(0)→ q2
q2 →(0)→ q2,   q2 →(1)→ q3
q3 →(0)→ q3,   q3 →(1)→ q2

Using Arden's Theorem to solve state equations:
R1 = ε + R1·1 (q1 has incoming loop 1, and ε since it is start)
R2 = R1·0 + R2·0 + R3·1
R3 = R2·1 + R3·0

Solving for R1:
R1 = ε + R1·1 ⇒ R1 = 1*

Solving for R3:
R3 = R2·1 + R3·0 ⇒ R3 = (R2·1)0* ⇒ R3 = R2·10*

Substitute R1 and R3 into R2:
R2 = (1*)·0 + R2·0 + (R2·10*)·1
R2 = 1*0 + R2(0 + 10*1)
Applying Arden's theorem (R = Q + RP ⇒ R = QP*):
R2 = 1*0(0 + 10*1)*

Since q2 is the only final state, the regular expression for the DFA is the expression for R2:
Regex = 1*0(0 + 10*1)*

Given e-NFA Transitions:

1. Compute ε-closures:
- ε-closure(p): Start at {p}. p→r (ε), so add {r}. r→p,q (ε), so add {q}. Total = {p, q, r}.
- ε-closure(q): Start at {q}. No ε transitions from q. Total = {q}.
- ε-closure(r): Start at {r}. r→p,q (ε), so add {p, q}. Total = {p, q, r}.

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

Find transitions from A {p, q, r}:
- On input 'a':
δ({p,q,r}, a) = δ(p,a) ∪ δ(q,a) ∪ δ(r,a) = {q} ∪ {p} ∪ {r} = {p, q, r}.
ε-closure({p, q, r}) = {p, q, r} = State A.
- On input 'b':
δ({p,q,r}, b) = δ(p,b) ∪ δ(q,b) ∪ δ(r,b) = {p,r} ∪ φ ∪ {p} = {p, r}.
ε-closure({p, r}) = ε-closure(p) ∪ ε-closure(r) = {p, q, r} ∪ {p, q, r} = {p, q, r} = State A.

Resulting DFA:
The converted DFA has a single state A (Start & Final) with a self-loop for both 'a' and 'b'.
Language accepted: (a + b)*.

Definition of Chomsky Normal Form (CNF):
A Context-Free Grammar is in CNF if all its production rules are of the form:
1. A → BC (A non-terminal generates exactly two non-terminals)
2. A → a (A non-terminal generates exactly one terminal)
Where A, B, C are non-terminals, and 'a' is a terminal.

Conversion of the given CFG to CNF:
Original Grammar: S → aSb | ab | Aa,   A → aab

Step 1: Replace terminals with new non-terminals
Let X_a → a, and X_b → b.
Substitute in original rules:
S → X_a S X_b | X_a X_b | A X_a
A → X_a X_a X_b

Step 2: Restrict RHS to exactly two non-terminals
For S → X_a S X_b, introduce S₁ → S X_b. Then S → X_a S₁.
For A → X_a X_a X_b, introduce A₁ → X_a X_b. Then A → X_a A₁.

Final CNF Grammar:

Useless Production: A production is useless if its symbols are unreachable from the start symbol, or if it contains non-terminals that cannot derive any string of terminals (non-generating).

Given Grammar:
A → bA | Bba | aa
B → aba | b | D
C → CA | AC | B
D → a | ε
(Assuming A is the Start Symbol as it is listed first)

1. Eliminate ε-productions:
- Nullable variables: D → ε, so D is nullable. B → D, so B is nullable. C → B, so C is nullable.
- Add rules simulating the absence of nullable variables:
In A → Bba, B is nullable, add A → ba.
In C → CA | AC, C is nullable, add C → A.
- Remove D → ε.
Grammar after ε-elimination:
A → bA | Bba | ba | aa
B → aba | b | D
C → CA | AC | A | B
D → a

2. Eliminate Unit productions:
- Unit pairs (X → Y): (B → D), (C → B), (C → D), (C → A).
- Resolve B → D: Add D's rules to B. B → a.
- Resolve C → B, C → A, C → D: Add B, A, D rules to C.
Grammar after Unit-elimination:
A → bA | Bba | ba | aa
B → aba | b | a
C → CA | AC | aba | b | a | bA | Bba | ba | aa
D → a

3. Eliminate Useless productions:
- Check generating symbols: D generates 'a', B generates 'b', A generates 'aa', C generates 'a'. All variables generate terminals.
- Check reachable symbols from Start Symbol (A):
From A, we can reach 'A' (via bA) and 'B' (via Bba).
C and D are completely unreachable from A.
- Remove unreachable symbols C and D and their productions.
Final Reduced Grammar:

Deterministic Pushdown Automaton (DPDA):
A PDA is deterministic if for any given state, input symbol (or ε), and top-of-stack symbol, there is at most one valid transition. Furthermore, if an ε-transition is defined for a specific state and stack symbol, no input-consuming transition can be defined for that same state and stack symbol. A DPDA parses unambiguously and is used for parsing deterministic context-free languages (like in most programming languages).

Non-deterministic Pushdown Automaton (NPDA):
An NPDA allows multiple possible transitions for the same state, input symbol (or ε), and stack symbol. It can "guess" paths and backtrack. NPDAs are strictly more powerful than DPDAs, meaning there exist context-free languages (like palindromes of even length) that can only be accepted by an NPDA and not by any DPDA.

We can construct a PDA that simulates top-down parsing (acceptance by empty stack) of the given CFG. The PDA starts by pushing the start symbol 'S' onto the stack and continually replaces non-terminals on the stack with their right-hand sides, while popping terminals when they match the input stream.

States: Q = {q}, Σ = {a, b}, Γ = {S, A, a, b}

Transitions (δ):

The PDA accepts if the input string is completely consumed and the stack becomes empty simultaneously.

(a) Pumping Lemma for Regular Languages:
If a language L is regular, then there exists a pumping length 'p' > 0 such that any string 'w' ∈ L with length |w| ≥ p can be divided into three parts, w = xyz, satisfying the following conditions:
1. |xy| ≤ p
2. |y| > 0 (y is not empty)
3. For all i ≥ 0, the string xyⁱz ∈ L.

(b) Pumping Lemma for Context-Free Languages:
If a language L is context-free, then there exists a pumping length 'p' > 0 such that any string 'w' ∈ L with length |w| ≥ p can be divided into five parts, w = uvxyz, satisfying the following conditions:
1. |vxy| ≤ p
2. |vy| > 0 (v and y cannot both be empty)
3. For all i ≥ 0, the string uvⁱxyⁱz ∈ L.

(c) Proof that L = {aⁿbⁿ | n ≥ 0} is not regular:
Assume, for the sake of contradiction, that L is regular.
1. Let 'p' be the pumping length given by the Pumping Lemma.
2. Choose a specific string w = a^pb^p. Clearly, w ∈ L and |w| = 2p ≥ p.
3. According to the Lemma, w can be divided into w = xyz such that |xy| ≤ p and |y| > 0.
4. Since the first 'p' characters of w are all 'a's, and |xy| ≤ p, the substring 'y' must consist entirely of 'a's. Let y = a^k where k > 0.
5. The Lemma states that for any i ≥ 0, xyⁱz must be in L. Let us pump the string by choosing i = 2.
6. The pumped string is xy²z = a^p+kb^p.
7. Because k > 0, the number of 'a's (p+k) is strictly greater than the number of 'b's (p). This pumped string does not belong to L.
8. This contradicts the Pumping Lemma. Therefore, our assumption is false, and L is not regular.

Greibach Normal Form (GNF) requires all productions to start with exactly one terminal, followed by any number of non-terminals (A → aα).

Step 1: Check for Left Recursion (Aim: A_i → A_jα where i < j)
- A1 → A2 A3 (Valid: 1 < 2)
- A2 → A3 A1 | b (Valid: 2 < 3)
- A3 → A1 A2 | a (Invalid: 3 ≮ 1)

Step 2: Eliminate invalid sequences through backward substitution into A3
Substitute A1 in A3:
A3 → (A2 A3) A2 | a
A3 → A2 A3 A2 | a (Still invalid: 3 ≮ 2)

Substitute A2 in A3:
A3 → (A3 A1 | b) A3 A2 | a
A3 → A3 A1 A3 A2 | b A3 A2 | a
Now A3 has immediate left recursion (A3 → A3α | β).

Step 3: Eliminate Immediate Left Recursion on A3
Let α = A1 A3 A2 and β = b A3 A2 | a.
Introduce a new non-terminal Z:
A3 → b A3 A2 | a | b A3 A2 Z | a Z
Z → A1 A3 A2 | A1 A3 A2 Z
(Note: All A3 productions now correctly start with terminals!)

Step 4: Substitute A3 back into A2 to obtain GNF for A2
A2 → (b A3 A2 | a | b A3 A2 Z | a Z) A1 | b
A2 → b A3 A2 A1 | a A1 | b A3 A2 Z A1 | a Z A1 | b
(Note: All A2 productions now correctly start with terminals!)

Step 5: Substitute A2 back into A1 to obtain GNF for A1
A1 → (b A3 A2 A1 | a A1 | b A3 A2 Z A1 | a Z A1 | b) A3
A1 → b A3 A2 A1 A3 | a A1 A3 | b A3 A2 Z A1 A3 | a Z A1 A3 | b A3
(Note: All A1 productions now correctly start with terminals!)

Step 6: Ensure Z is in GNF by substituting A1
Since Z → A1 A3 A2 | A1 A3 A2 Z, and all A1 productions start with a terminal, we replace A1 with its 5 right-hand sides in both terms.
This yields 10 productions for Z, all starting with 'a' or 'b'. For brevity, we substitute A1 into Z:
Z → (RHS of A1) A3 A2 | (RHS of A1) A3 A2 Z

Final Grammar in GNF: