FLAT 2024

(I) What type of grammar is Context-sensitive grammar?

Context-sensitive grammar is classified as a Type-1 grammar in the Chomsky hierarchy.

(II) Give two applications of TM.

1. Used as a theoretical model for studying the limits of computability and proving problems as decidable or undecidable.
2. Used in computational complexity theory to define and analyze complexity classes like P and NP.

(III) What is a universal Turing machine?

A Universal Turing Machine (UTM) is a Turing machine capable of simulating any other arbitrary Turing machine. It takes as input the encoded description of the machine to be simulated along with its input string, and produces the same output that the simulated machine would.

(IV) Give two applications of Context free languages.

1. Designing parsers for programming languages in compilers.
2. Describing the syntax of document formats like XML and HTML (e.g., using Document Type Definitions).

(V) Give two examples/applications designed as finite state systems.

1. Traffic light controllers and vending machines.
2. Lexical analyzers (scanners) in compilers used to tokenize source code.

(VI) What is context-free language?

A context-free language (CFL) is a formal language generated by a context-free grammar (CFG) or accepted by a pushdown automaton (PDA). In its grammar, all production rules are strictly of the form A → γ, where a single non-terminal (A) maps to a string of terminals and/or non-terminals (γ).

(VII) Define context sensitive grammar.

A context-sensitive grammar (CSG) is a formal grammar where the production rules are of the form αAβ → αγβ. Here, A is a non-terminal, and α, β, and γ are strings of terminals and/or non-terminals (with γ not empty). The replacement of A by γ depends on its surrounding context α and β.

(VIII) How can you proceed for Turing machine construction?

To construct a Turing machine, one specifies a 7-tuple (Q, Σ, Γ, δ, q₀, q_accept, q_reject). Practically, one proceeds by defining states to remember the current phase of computation, deciding how to encode information on the tape, and defining the transition function (δ) which dictates reading the current tape symbol, writing a new symbol, moving the head Left/Right, and transitioning to the next state.

(IX) What are the various representation of TM?

1. Transition diagram (State diagram): A directed graph representing states and transitions.
2. Transition table: A tabular representation of the transition function δ.
3. Instantaneous Descriptions (IDs): A string representation of the overall state of the computation at any step (e.g., αqβ).

(X) Define finite automaton.

A finite automaton is a mathematical model of computation consisting of a finite set of states (Q), a finite input alphabet (Σ), a transition function (δ), a start state (q₀), and a set of final/accepting states (F). It has no memory (other than its current state) and is used to recognize regular languages.

(XI) What do you mean by k-equivalent states?

Two states 'p' and 'q' of a deterministic finite automaton are said to be k-equivalent if there is no input string of length ≤ k that distinguishes them. This means for all strings of length ≤ k, traversing from both 'p' and 'q' will either both lead to final states, or both lead to non-final states.

(XII) When a grammar is said to be ambiguous?

A grammar is said to be ambiguous if it can generate at least one string in its language that has more than one distinct leftmost derivation, more than one distinct rightmost derivation, or correspondingly, more than one distinct parse tree.

Since k = n + 2m, we can substitute k in the language definition:
L = {aⁿ b^m c^(n+2m) | n ≥ 0, m ≥ 0}

This can be rewritten and grouped as:
L = {aⁿ (b^m c^2m) cⁿ | n ≥ 0, m ≥ 0}

We can construct a grammar where a non-terminal S generates the outer an ... cn part, and another non-terminal A generates the inner bm c2m part.

Grammar G = (V, Σ, P, S)
V = {S, A}
Σ = {a, b, c}
Productions (P):
S → aSc | A
A → bAcc | ε

Explanation:
- The rule S → aSc recursively adds one 'a' at the beginning and one 'c' at the end, ensuring that for every 'a', there is one 'c'.
- The rule S → A transitions to generating the inner part once the outer a's and c's are matched.
- The rule A → bAcc recursively adds one 'b' and two 'c's, ensuring that for every 'b', there are exactly two 'c's.
- The rule A → ε terminates the derivation.

A Universal Turing Machine (UTM) is a special Turing machine that can simulate the behavior of any other arbitrary Turing machine on any given input.

Concept: In standard Turing machines, the "hardware" (transition rules) is fixed for a specific computational task. A UTM acts like a programmable general-purpose computer. It takes the description (program) of the machine to be simulated as input, along with the data.

Operation: The input tape of a UTM typically contains two parts separated by a special marker:
1. The encoded description of the simulated Turing machine (M).
2. The input string (w) to be processed by M.

Simulation Process: The UTM maintains the simulated state of M and its current head position on the simulated tape. It reads the current state and tape symbol, scans the description of M on its tape to find the appropriate transition rule, and then updates the simulated tape, state, and head position accordingly.

Significance: The UTM concept forms the theoretical foundation for modern stored-program computers (von Neumann architecture) and software execution, proving that a single machine can perform any computable task if provided with the correct instructions.

A grammar is ambiguous if there exists at least one string in its language that has two different leftmost derivations (or two different parse trees).

Let us consider the string w = abab.

Leftmost Derivation 1:
S ⇒ aSbS
⇒ a(bSaS)bS     (applying S → bSaS to the 1st S)
⇒ abSaSbS       (simplified)
⇒ abaSbS        (applying S → λ to the 1st S)
⇒ ababS         (applying S → λ to the 2nd S)
⇒ abab          (applying S → λ to the 3rd S)

Leftmost Derivation 2:
S ⇒ aSbS
⇒ a(λ)bS        (applying S → λ to the 1st S)
⇒ abS           (simplified)
⇒ ab(aSbS)      (applying S → aSbS to the 2nd S)
⇒ abaSbS        (applying S → λ to the 1st S in parenthesis)
⇒ ababS         (applying S → λ to the 2nd S in parenthesis)
⇒ abab          (applying S → λ to the last S)

Since the string "abab" has two distinct leftmost derivations, the given grammar is ambiguous.

Let's analyze the strings generated by this grammar by applying the rules sequentially:

• Applying rule 2 directly: S ⇒ ε
• Applying rule 1 once: S ⇒ aSb ⇒ a(ε)b = ab
• Applying rule 1 twice: S ⇒ aSb ⇒ a(aSb)b = a²Sb² ⇒ a²(ε)b² = a²b²
• Applying rule 1 'n' times: S ⇒ aⁿSbⁿ ⇒ aⁿ(ε)bⁿ = aⁿbⁿ

Because every application of the recursive rule S → aSb adds exactly one 'a' on the left and one 'b' on the right symmetrically, the number of 'a's will always strictly equal the number of 'b's, and all 'a's will precede all 'b's.

Therefore, the language generated by the grammar is:
L(G) = {aⁿbⁿ | n ≥ 0}

The Halting Problem is a fundamental concept in computability theory introduced by Alan Turing. It poses the following question:
Given a description of an arbitrary Turing machine M and an input string w, is it possible to determine (via a general algorithm) whether M will eventually halt and produce an answer, or will it run forever in an infinite loop?

Result: Turing mathematically proved that the Halting Problem is undecidable. This means that there cannot exist a universal algorithm (or Turing machine) that can always correctly output "Yes, it halts" or "No, it loops forever" for every possible (M, w) pair in a finite amount of time.

Proof Idea: The proof relies on a contradiction argument (diagonalization). If a theoretical machine H could decide the halting problem, one could construct a paradox machine P that queries H about what P itself will do. P then deliberately does the exact opposite of H's prediction (halts if H says it loops, and loops if H says it halts). This paradox proves that the decider machine H cannot exist.

Simplification of a Context-Free Grammar (CFG) involves converting it into an equivalent grammar without unnecessary or problematic productions.

(a) Removing useless productions:
A symbol is useless if it does not participate in the derivation of any string of terminals. It involves two steps:
1. Eliminate non-generating symbols: Symbols that can never derive a string consisting entirely of terminals.
2. Eliminate unreachable symbols: Symbols that can never be reached from the start symbol.
Example:
S → AB | a
A → b
B → bB
- B is non-generating because any derivation from B will always contain B (it never terminates). We remove B and any production containing it (S → AB).
- New grammar: S → a, A → b.
- Now, A is unreachable from the start symbol S. We remove A → b.
- Simplified grammar: S → a

(b) Removing λ-production (null production):
A λ-production is of the form A → λ (or ε). To remove them:
1. Identify all nullable variables (variables that can eventually derive λ).
2. For every production A → α containing a nullable variable on the RHS, add new productions where that variable is replaced by λ in all possible combinations.
3. Remove the original A → λ rules.
Example:
S → ABC
A → aA | λ
B → bB | λ
C → c
- Nullable variables: A and B.
- Add combinations for A and B being null in S, A, and B rules:
- Simplified grammar:
S → ABC | BC | AC | C
A → aA | a
B → bB | b
C → c

(c) Removing unit production:
A unit production is of the form A → B, where A and B are non-terminals. To remove them:
1. Identify all unit pairs (A, B) such that A can derive B using one or more unit productions (A ⇒* B).
2. For each pair (A, B), if there is a non-unit production B → α, add a new production A → α.
3. Remove all original unit productions.
Example:
S → A | a
A → B
B → b
- Unit pairs: (S, A), (A, B), and transitively (S, B).
- For (A, B): add A → b (since B → b is non-unit).
- For (S, B): add S → b.
- Remove S → A and A → B.
- Simplified grammar:
S → a | b
A → b
B → b

(a) What is Turing Machine?
A Turing machine is a mathematical model of computation consisting of an infinite tape divided into cells, a read/write head, and a finite control. Formally, it is defined as a 7-tuple: M = (Q, Σ, Γ, δ, q₀, q_accept, q_reject), where:
- Q: finite set of states
- Σ: input alphabet (not containing the blank symbol B)
- Γ: tape alphabet, where Σ ⊂ Γ and B ∈ Γ
- δ: transition function mapping Q × Γ → Q × Γ × {L, R}
- q₀: start state
- q_accept: accepting state
- q_reject: rejecting state

(b) How can Turing Machines be used as language acceptors?
A Turing Machine acts as a language acceptor by taking an input string on its tape and executing its state transitions step-by-step.
- If the machine eventually transitions to the accept state (q_accept), it halts immediately, and the input string is considered accepted.
- If it reaches the reject state (q_reject) or if it runs infinitely without ever reaching the accept state, the string is not accepted.
The set of all strings accepted by a TM forms its language. Such languages are known as Recursively Enumerable languages.

(c) Design TM for regular expression 00* over Σ = {0, 1}
The regular expression 00* signifies that the string must start with a '0', followed by zero or more '0's. It should strictly contain no '1's. Valid strings: "0", "00", "000".
Logic:
1. Read the first symbol. If it is '0', move right and go to state q₁ to check the rest. If it is '1' or Blank (B), reject.
2. In q₁, read remaining symbols. As long as we see '0', keep moving right. If we see '1', reject. If we see 'B', we have reached the end of a valid string, so move to an accept state.
Transition Table:

Current State	Input Symbol	Write Symbol	Move	Next State
q0 (Start)	0	0	R	q1
q0	1	-	-	Reject
q0	B	-	-	Reject
q1	0	0	R	q1
q1	1	-	-	Reject
q1	B	B	L	qaccept

(a) When a Problem is said to be Undecidable?
A problem is said to be undecidable if there does not exist any Turing machine (or general computational algorithm) that can always solve it and halt with the correct "yes" or "no" answer for every possible input instance. While an algorithm might find the correct answer for specific cases, it is mathematically proven that no universal algorithm exists that guarantees a halt and correct answer for all inputs. Famous examples include the Halting Problem and the Post Correspondence Problem.

(b) Grammar for L = {aⁿ b^m : n ≥ 0, m < n}
Since m < n, we can express n as n = m + k, where k ≥ 1.
Thus, the strings are of the form: a(m+k) bm = ak (am bm).
This means every valid string consists of a prefix of one or more 'a's, followed by an equal number of 'a's and 'b's.
Grammar:
S → A B
A → aA | a     (Generates prefix a^k for k ≥ 1)
B → aBb | ε    (Generates suffix a^m b^m for m ≥ 0)

(c) Show that the grammars are not equivalent:
Two grammars are equivalent if they generate the exact same language (i.e., L(G₁) = L(G₂)).
Let G₁: S → aSb | bSa | SS | a
Let G₂: S → aSb | bSa | a
Consider the string w = "aa".
- In G₁: We can derive "aa" using the derivation: S ⇒ SS ⇒ aS ⇒ aa. Thus, "aa" ∈ L(G₁).
- In G₂: Let's examine the productions. The base case S → a produces a string with 1 'a' and 0 'b's. The recursive rules S → aSb and S → bSa each append exactly one 'a' and one 'b' to the derived string. Therefore, every derivation step maintains the invariant property that:
Total number of 'a's = Total number of 'b's + 1.
For the string "aa", the number of 'a's is 2 and 'b's is 0. Since 2 ≠ 0 + 1, it is impossible for G₂ to generate "aa".
Since "aa" is in L(G₁) but not in L(G₂), we conclude that L(G₁) ≠ L(G₂). The grammars are not equivalent.

(a) DFA for L = {aⁿ : n = 3 or n is even}
The alphabet is Σ = {a}. The string length must be 3, or an even number (0, 2, 4, 6...). We construct states to count the length up to 5, after which the even/odd parity repeats.
States:
- q₀ (Start, Final): length 0 (even)
- q₁: length 1 (odd)
- q₂ (Final): length 2 (even)
- q₃ (Final): length 3 (special case)
- q₄ (Final): length 4 (even)
- q₅: length 5 (odd, repeats parity with q₄)
Transitions:
δ(q₀, a) = q₁
δ(q₁, a) = q₂
δ(q₂, a) = q₃
δ(q₃, a) = q₄
δ(q₄, a) = q₅
δ(q₅, a) = q₄

(b) DFA for all strings with an even number of a's, Σ = {a, b}
States:
- q₀ (Start, Final): Represents an even number of 'a's seen so far.
- q₁: Represents an odd number of 'a's seen so far.
Transitions:
δ(q₀, a) = q₁,   δ(q₀, b) = q₀
δ(q₁, a) = q₀,   δ(q₁, b) = q₁

(c) DFA for all strings with exactly one a, Σ = {a, b}
States:
- q₀ (Start): 0 'a's seen.
- q₁ (Final): Exactly 1 'a' seen.
- q₂ (Trap state): More than 1 'a' seen.
Transitions:
δ(q₀, a) = q₁,   δ(q₀, b) = q₀
δ(q₁, a) = q₂,   δ(q₁, b) = q₁
δ(q₂, a) = q₂,   δ(q₂, b) = q₂

The Chomsky hierarchy (introduced by Noam Chomsky) classifies formal grammars, languages, and automata into four distinct categories based on the restrictions applied to their production rules. As the type number increases, the restrictions increase, making the languages simpler and less expressive.

1. Type-0: Unrestricted Grammars
- Language Category: Recursively Enumerable (RE) Languages.
- Accepting Machine: Turing Machine (TM).
- Rule Restriction: Production rules are of the form α → β, where α and β can be any string of terminals and non-terminals, provided α contains at least one non-terminal. There are absolutely no restrictions on the lengths of the strings.
- Example Language: The Halting problem language, or complex computational logic.

2. Type-1: Context-Sensitive Grammars (CSG)
- Language Category: Context-Sensitive Languages (CSL).
- Accepting Machine: Linear Bounded Automaton (LBA).
- Rule Restriction: Productions are of the form αAβ → αγβ, meaning non-terminal A can be replaced by γ only in the context of α and β. Additionally, the length condition |left side| ≤ |right side| must rigorously hold (except possibly for S → ε if S doesn't appear on the right).
- Example Language: L = {aⁿbⁿcⁿ | n ≥ 1}. This cannot be parsed by a Pushdown Automaton because it requires matching three counts simultaneously.

3. Type-2: Context-Free Grammars (CFG)
- Language Category: Context-Free Languages (CFL).
- Accepting Machine: Pushdown Automaton (PDA).
- Rule Restriction: Productions are strictly of the form A → γ, where A is a single non-terminal and γ is any string of terminals and/or non-terminals. The surrounding context does not matter.
- Example Language: L = {aⁿbⁿ | n ≥ 1} (Palindromes). PDAs can count and match nested dependencies using a single stack.

4. Type-3: Regular Grammars
- Language Category: Regular Languages.
- Accepting Machine: Finite Automaton (DFA/NFA).
- Rule Restriction: Productions must be either purely right-linear (A → aB or A → a) or purely left-linear (A → Ba or A → a), where A and B are non-terminals and 'a' is a terminal (or string of terminals).
- Example Language: L = a*b* (Strings matching a regular expression). Used heavily in lexical analysis.

Hierarchy containment: Regular ⊂ Context-Free ⊂ Context-Sensitive ⊂ Recursively Enumerable.