Formal Language & Automata Theory important questions.

a) What is a formal language and how is it different from a natural language?

a) What is a formal language, and how is it different from a natural language?

Answer:

Formal Language:

• Defined with mathematical/precise definitions
• Follows fixed, strict rules (grammar)
• No ambiguity — each string has only one meaning
• Machine-readable — computers can understand

Natural Language:

• Used for human communication (English, Hindi)
• Has flexible rules with exceptions
• Ambiguous — one sentence can have multiple meanings
• Context-dependent

Comparison Table:

Formal LanguageNatural Language{aⁿbⁿ | n≥1}"I saw a man with a telescope"UnambiguousAmbiguousStrict grammarFlexible grammarFor computersFor humansNo exceptionsMany exceptions

Examples:

Formal Language: 
L = {ab, aabb, aaabbb}
Clear, precise, no ambiguity

Natural Language: 
"Time flies like an arrow"
Multiple interpretations possible:
- Time moves quickly like an arrow
- Measure the speed of flies like you measure arrows
- A type of fly called "time flies" enjoys arrows

b) Define the term “alphabet” in the context of formal languages.

Answer:

Alphabet (Σ): An alphabet is a finite, non-empty set of symbols used to construct strings.

Properties:

• Must be finite (limited number of symbols)
• Must be non-empty (at least one symbol)
• Symbols are indivisible (atomic units)

Examples:

1. Σ = {0, 1}          (Binary alphabet)
2. Σ = {a, b, c}       (Three-symbol alphabet)
3. Σ = {x, y, z}       (Variable names)
4. Σ = {0,1,2,...,9}   (Decimal digits)

Strings over Σ:

If Σ = {a, b}
Valid strings: ε, a, b, aa, ab, ba, bb, aaa, aab, ...
Σ* = {ε, a, b, aa, ab, ba, bb, aaa, ...}
(Σ* represents all possible strings including empty string)

Important Notations:

Σ+ = All non-empty strings over Σ
Σ* = Σ+ ∪ {ε} (includes empty string)
|Σ| = Number of symbols in alphabet

c) How do we represent Grammar?

Answer:

Grammar Representation: Grammar is represented as a 4-tuple:

G = (V, T, P, S)

Where:

• V (Variables) = Set of non-terminal symbols
• T (Terminals) = Set of terminal symbols (alphabet)
• P (Productions) = Set of production rules
• S (Start Symbol) = Starting non-terminal (S ∈ V)

Constraints:

• V ∩ T = ∅ (no overlap between terminals and non-terminals)
• S ∈ V (start symbol must be a non-terminal)

Example 1:

G = ({S, A}, {a, b}, P, S)

Production Rules P:
S → aA
A → aA | b

Language generated: {aⁿb | n ≥ 1}
Strings: ab, aab, aaab, aaaab, ...

Example 2:

G = ({S}, {a, b}, P, S)

P: S → aSb | ε

Language: {aⁿbⁿ | n ≥ 0}
Strings: ε, ab, aabb, aaabbb, ...

Derivation Example:

Grammar: S → aA, A → aA | b

Derivation of string "aab":
S ⇒ aA 
  ⇒ aaA 
  ⇒ aab

String "aab" is generated ✓

Components Explanation:

V = {S, A, B}      - Variables (can be replaced)
T = {a, b, c}      - Terminals (final symbols)
P = {S → aB, ...}  - Rules for replacement
S = Starting point - Derivation begins here

d) Define NDFA.

Answer:

NDFA (Non-Deterministic Finite Automaton):

NDFA is a finite automaton where multiple transitions are possible from a state on the same input symbol.

Formal Definition: NDFA = (Q, Σ, δ, q₀, F)

Where:

• Q = Finite set of states
• Σ = Input alphabet
• δ: Q × (Σ ∪ {ε}) → 2^Q = Transition function (returns a set of states)
• q₀ = Start state
• F ⊆ Q = Set of final/accepting states

Key Properties:

1. Multiple transitions allowed from one state on same input
2. ε-transitions allowed (move without consuming input)
3. Non-deterministic choice at each step
4. String is accepted if ANY path reaches a final state

Example:

NDFA for strings ending with 'ab':

States: Q = {q0, q1, q2}
Alphabet: Σ = {a, b}
Start state: q0
Final states: F = {q2}

Transition Table:
┌─────┬─────────┬─────────┐
│State│    a    │    b    │
├─────┼─────────┼─────────┤
│ q0  │ {q0,q1} │  {q0}   │  ← Multiple states for 'a'!
│ q1  │   ∅     │  {q2}   │
│ q2  │   ∅     │   ∅     │
└─────┴─────────┴─────────┘

String "aab" acceptance:
Path 1: q0 -a→ q0 -a→ q0 -b→ q0 (Rejected, q0 not final)
Path 2: q0 -a→ q0 -a→ q1 -b→ q2 (Accepted, q2 is final) ✓

Since at least ONE path reaches final state, strin

Difference from DFA:

DFA: δ(q0, a) = q1         (Single state - deterministic)
NDFA: δ(q0, a) = {q1, q2}  (Multiple states - non-deterministic)

e) The regular expression ab*c will give?

Answer:

*Regular Expression: abc**

Meaning:

• a — exactly one ‘a symbol
• **b*** — zero or more ‘b’ symbols (Kleene star)
• c — exactly one ‘c’ symbol

Language Generated:

L = {abⁿc | n ≥ 0}

All Possible Strings:

n=0:  ac       (a, zero b's, c)
n=1:  abc      (a, one b, c)
n=2:  abbc     (a, two b's, c)
n=3:  abbbc    (a, three b's, c)
n=4:  abbbbc   (a, four b's, c)
...and so on

Complete Language:

L = {ac, abc, abbc, abbbc, abbbbc, abbbbbc, ...}

Accepted Strings:

✓ ac
✓ abc
✓ abbc
✓ abbbbbbbc

NOT Accepted Strings:

✗ bc       (missing 'a' at start)
✗ ab       (missing 'c' at end)
✗ abcb     (extra 'b' after 'c')
✗ aac      (wrong - should be 'b' not 'a')
✗ abcc     (extra 'c' at end)
✗ cabc     (starts with 'c' instead of 'a')

*Finite Automaton for abc:**

b (loop)
        ↻
→ q0 -a→ q1 -c→ q2(final)

States:
q0: Start state
q1: Seen 'a', waiting for b's or c
q2: Final state (seen 'c')

f) What is context-sensitive grammar?

Answer:

Context-Sensitive Grammar (CSG):

CSG is a Type-1 grammar where production rules have the form: αAβ → αγβ

Where:

• A = single non-terminal being replaced
• α, β = context (strings of terminals/non-terminals, can be ε)
• γ = non-empty string of terminals/non-terminals
• |αAβ| ≤ |αγβ| (non-contracting — length doesn’t decrease)

Properties:

1. Length non-decreasing (except S → ε if S doesn’t appear on RHS)
2. Context matters — replacement depends on surrounding symbols
3. Recognised by Linear Bounded Automaton (LBA)
4. More powerful than CFG, less powerful than unrestricted grammar

Example 1: Simple CSG

Production: AB → BA

This swaps A and B, but only when:
- A appears with B on its right (context!)
- Not just any A can become B

Example derivation:
ABAB → BAAB → BABA → BBAA

Example 2: Language {aⁿbⁿcⁿ | n ≥ 1}

Context-Sensitive Grammar:

S → abc | aSBc
CB → BC
aB → ab
bB → bb
bC → bc
cC → cc

Derivation for "aabbcc" (n=2):
S ⇒ aSBc           (apply S → aSBc)
  ⇒ aabcBc         (apply S → abc)
  ⇒ aabBcc         (apply CB → BC)
  ⇒ aabbcc         (apply bB → bb)

String "aabbcc" generated ✓

Example 3: Detailed CSG

Grammar for L = {aⁿbⁿcⁿ | n ≥ 1}

Productions:
1. S → aSBC | aBC     (generate structure)
2. CB → BC            (rearrange B's and C's)
3. aB → ab            (convert in context)
4. bB → bb            (convert in context)
5. bC → bc            (convert in context)
6. cC → cc            (convert in context)

Why Context-Sensitive?
- Rule "aB → ab" only applies when 'a' is on left
- Rule "bC → bc" only applies when 'b' is on left
- Context (neighboring symbols) determines applicability

Chomsky Hierarchy Position:

Type-0 (Unrestricted):  α → β (any string to any string)
Type-1 (CSG):           αAβ → αγβ (context-sensitive)
Type-2 (CFG):           A → γ (context-free)
Type-3 (Regular):       A → aB or A → a

Why “Context-Sensitive”?

In production αAβ → αγβ:
- α (left context) and β (right context) remain unchanged
- Only A is replaced by γ
- Replacement depends on what symbols surround A

g) Define LBA.

Answer:

LBA (Linear Bounded Automaton):

LBA is a restricted Turing Machine whose tape space is bounded by a linear function of the input length.

Formal Definition: An LBA is a Turing Machine where:

• Tape length is limited to c × n (c = constant, n = input length)
• Tape cannot extend beyond input boundaries
• Recognzes Context-Sensitive Languages (CSL)

Formal Notation:

LBA = (Q, Σ, Γ, δ, q₀, F, ⊢, ⊣)

Q = Finite set of states
Σ = Input alphabet
Γ = Tape alphabet (Σ ⊆ Γ)
δ = Transition function
q₀ = Start state
F = Set of final states
⊢ = Left end marker (cannot overwrite)
⊣ = Right end marker (cannot overwrite)

Key Properties:

1. Bounded tape — Uses O(n) space where n = input length
2. Cannot move beyond end markers ⊢ and ⊣
3. More powerful than PDA (recognizes CSL, not just CFL)
4. Less powerful than general TM (tape is bounded)

Components:

Input: "aabbcc"

Tape structure:
⊢ a a b b c c ⊣
↑             ↑
Left          Right
end marker    end marker
(fixed)       (fixed)

Tape cells = input length + 2 (for markers)
Head cannot cross markers

Example: Recognizing L = {aⁿbⁿcⁿ | n ≥ 1}

Input: "aabbcc" (length = 6)
Tape space: 6 cells (bounded!)

LBA Algorithm:
Step 1: Mark first 'a' as X
        X a b b c c
Step 2: Find first 'b', mark as Y
        X a Y b c c
Step 3: Find first 'c', mark as Z
        X a Y b Z c
Step 4: Return to start, repeat
        X X Y Y Z Z
Step 5: If all symbols matched equally → ACCEPT
        Otherwise → REJECT

All operations within 6-cell boundary ✓

Complexity Hierarchy:

Regular Languages    <  Context-Free     <  Context-Sensitive  <  Recursively Enumerable
       ↓                      ↓                    ↓                      ↓
Finite Automaton (FA)   Pushdown (PDA)    Linear Bounded (LBA)   Turing Machine (TM)
   O(1) space            O(n) stack           O(n) tape            Unbounded tape

LBA vs TM:

FeatureLBATuring MachineTape sizeBounded (O(n))UnboundedSpaceLinearUnlimitedPowerCSLRE (Recursively Enumerable)HaltingAlways halts (decidable)May not halt

Applications:

1. Natural language syntax checking
2. Context-sensitive compiler features
3. String matching with context

h) What is an NP NP-Complete problem?

Answer:

NP-Complete Problem:

A problem is NP-Complete if it satisfies TWO conditions:

1. The problem is in NP (solution can be verified in polynomial time)
2. The problem is NP-Hard (all NP problems can be reduced to it in polynomial time)

Formal Definition:

NP-Complete = NP ∩ NP-Hard

A problem L is NP-Complete if:
1. L ∈ NP (verifiable in polynomial time)
2. Every problem in NP is polynomial-time reducible to L

Key Properties:

1. Hardest problems in the NP class
2. If ANY NP-Complete problem has a polynomial solution → P = NP (the biggest unsolved problem in CS)
3. No known polynomial-time algorithm exists
4. Verification is easy; finding a solution is hard

Famous NP-Complete Problems:

1. SAT (Boolean Satisfiability) - First proved NP-Complete by Cook
2. 3-SAT
3. Vertex Cover
4. Hamiltonian Cycle
5. Travelling Salesman Problem (Decision version)
6. Graph Coloring (k-coloring)
7. Clique Problem
8. Subset Sum
9. Knapsack Problem (0/1)
10. Independent Set

Example 1: Vertex Cover Problem

Problem: Does graph G have a vertex cover of size ≤ k?
(Vertex cover = set of vertices that covers all edges)

Graph:    A---B
          |   |
          C---D

Question: Is there a vertex cover of size ≤ 2?

Answer: YES → {A, D} covers all edges
- Edge AB: covered by A ✓
- Edge AC: covered by A ✓
- Edge BD: covered by D ✓
- Edge CD: covered by D ✓

Verification: O(E) time - Easy! ✓
Finding optimal cover: Exponential - Hard! ✗

This is NP-Complete!

Example 2: 3-SAT Problem

Boolean Formula in CNF (3 literals per clause):
F = (x₁ ∨ x₂ ∨ x₃) ∧ (¬x₁ ∨ x₂ ∨ ¬x₄) ∧ (x₃ ∨ ¬x₄ ∨ x₅)

Question: Do values exist that make F = TRUE?

Given solution: x₁=T, x₂=T, x₃=F, x₄=F, x₅=T

Verification:
Clause 1: (T ∨ T ∨ F) = T ✓
Clause 2: (F ∨ T ∨ T) = T ✓
Clause 3: (F ∨ T ∨ T) = T ✓
All clauses TRUE → F = TRUE ✓

Verify: Polynomial O(n) ✓
Find: Try 2ⁿ combinations - Exponential ✗

Example 3: Hamiltonian Cycle

Problem: Does graph have cycle visiting each vertex exactly once?

Graph: A---B
       |\ /|
       | X |
       |/ \|
       C---D

Cycle: A → B → D → C → A ✓

Given cycle verification: O(V) - Easy ✓
Finding cycle: O(V!) - Hard ✗

Complexity Class Diagram:

All Problems
              |
        Decidable Problems
              |
      ┌───────┴───────┐
      |               |
   NP-Hard         P (Easy)
      |            (Polynomial)
      |
  NP-Complete
  (Hardest in NP)
      |
   ───┴───
  /       \
NP      P=NP?
(verify  (Unknown)
 easy)

Significance:

If we find polynomial algorithm for ONE NP-Complete problem,
then ALL NP problems can be solved in polynomial time!
This would prove P = NP (million dollar problem!)

i) Define Intractability.

Answer:

Intractability:

A problem is intractable if no polynomial-time algorithm exists to solve it, making it practically unsolvable for large inputs.

Definition: Problems are intractable when:

• No known polynomial-time algorithm (no O(nᵏ) solution)
• Best best-known algorithms have exponential or factorial time complexity
• For large inputs, the solution takes an unreasonably long time (years/centuries)

Time Complexity:

Intractable complexities:
- O(2ⁿ)    - Exponential
- O(n!)    - Factorial
- O(nⁿ)    - Polynomial exponential
- O(2^2ⁿ)  - Double exponential

Examples of Intractable Problems:

1. Travelling Salesman Problem (TSP)

Problem: Find shortest route visiting n cities exactly once

Brute force: Try all permutations
Time complexity: O(n!)

Example with n=20 cities:
20! = 2,432,902,008,176,640,000 operations
Even at 1 billion ops/sec = 77 years! ✗

For n=50: 50! ≈ 10⁶⁴ operations
(Age of universe = 10¹⁷ seconds) ✗

2. Subset Sum Problem

Problem: Given set S and target T, does subset exist with sum = T?

Set: {3, 5, 7, 11, 13}
Target: 18

Brute force: Check all subsets
Time: O(2ⁿ) where n = |S|

n=5:  2⁵ = 32 subsets (manageable)
n=50: 2⁵⁰ = 10¹⁵ subsets (intractable!)

3. Hamiltonian Cycle

Problem: Find path visiting each vertex exactly once

Time: O(n!) - factorial
Graph with 25 vertices: 25! ≈ 10²⁵ paths to check

4. Graph Colouring

Problem: Color graph with k colors (no adjacent same color)

Time: O(kⁿ) where n = vertices
For 50 vertices, 3 colors: 3⁵⁰ ≈ 10²⁴ combinations

Tractable vs Intractable:

Tractable (P)Intractable (NP-Hard/Complete)O(n), O(n log n), O(n²), O(n³)O(2ⁿ), O(n!), O(nⁿ)Sorting, SearchingTSP, Hamiltonian CycleBinary Search, DijkstraSubset Sum, KnapsackSolvable for large nUnsolvable for large nSeconds to minutesYears to centuries

Growth Rate Comparison:

Input size: n = 50

Tractable O(n²):
50² = 2,500 operations
Time: Microseconds ✓

Tractable O(n³):
50³ = 125,000 operations  
Time: Milliseconds ✓

Intractable O(2ⁿ):
2⁵⁰ = 1,125,899,906,842,624 operations
Time: 35 years (at 1M ops/sec) ✗

Intractable O(n!):
50! ≈ 3 × 10⁶⁴ operations
Time: Longer than age of universe! ✗

Real-World Impact Table:

nn²2ⁿn!101001,0243.6M204001M2.4 × 10¹⁸309001B2.6 × 10³²502,50010¹⁵3 × 10⁶⁴

Practical Implications:

Tractable: Can solve for n=1000, n=10000, even n=1000000
Intractable: Struggle with n=50, impossible for n=100

Example:
- Sorting 1M items: Few seconds (O(n log n)) ✓
- TSP with 100 cities: Billions of years (O(n!)) ✗

Approaches for Intractable Problems:

Since exact solutions infeasible, we use:
1. Approximation algorithms (good enough solution)
2. Heuristics (rules of thumb)
3. Randomized algorithms
4. Solve special cases only

j) Define NFA.

Answer:

NFA (Non-deterministic Finite Automaton):

An NFA is a finite automaton that allows multiple possible transitions from a state on the same input symbol and permits ε-transitions (moves without consuming input).

Formal Definition:

NFA = (Q, Σ, δ, q₀, F)

Where:

• Q = Finite set of states
• Σ = Input alphabet (finite set of symbols)
• δ: Q × (Σ ∪ {ε}) → 2^Q = Transition function (returns set of states)
• q₀ ∈ Q = Initial/start state
• F ⊆ Q = Set of final/accepting states

Key Characteristics:

1. Non-determinism:

Multiple next states possible for same input
δ(q₀, a) = {q₁, q₂}  ← Can go to q₁ OR q₂

Example 1: NFA for strings ending with “ab”

Alphabet: Σ = {a, b}
States: Q = {q₀, q₁, q₂}
Start state: q₀
Final states: F = {q₂}

Transition Table:
┌───────┬──────────┬──────────┐
│ State │    a     │    b     │
├───────┼──────────┼──────────┤
│  q₀   │ {q₀, q₁} │  {q₀}    │  ← Non-determinism!
│  q₁   │    ∅     │  {q₂}    │
│  q₂   │    ∅     │    ∅     │
└───────┴──────────┴──────────┘

State Diagram:
      a,b
       ↻
    → q₀ -a→ q₁ -b→ ((q₂))

String "aab" has TWO computation paths:

Path 1: q₀ -a→ q₀ -a→ q₀ -b→ q₀ ✗ (rejected, q₀ not final)
Path 2: q₀ -a→ q₀ -a→ q₁ -b→ q₂ ✓ (accepted, q₂ is final)

Since ONE path succeeds → String ACCEPTED ✓

*Example 3: NFA for (a+b)abb

Strings must end with "abb"

State diagram:
    a,b        a        b        b
  → q₀ ←→ q₁ --→ q₂ --→ q₃ --→ ((q₄))
     ↻

Transition table:
┌───────┬──────────┬──────────┐
│ State │    a     │    b     │
├───────┼──────────┼──────────┤
│  q₀   │ {q₀, q₁} │  {q₀}    │
│  q₁   │    ∅     │  {q₂}    │
│  q₂   │    ∅     │  {q₃}    │
│  q₃   │    ∅     │    ∅     │
└───────┴──────────┴──────────┘

NFA vs DFA Comparison:

FeatureDFANFATransitionExactly one next stateZero or more next statesε-movesNot allowedAllowedDeterminismDeterministic (predictable)Non-deterministic (multiple choices)Next stateδ(q, a) = q' (single state)δ(q, a) = {q₁, q₂, ...} (set)DesignMore complexEasier to designStatesMay need more statesUsually fewer statesExecutionFaster (single path)Slower (explore all paths)AcceptanceMust reach final stateAny path reaching final state

Conversion Example:

Given NFA:
δ(q₀, a) = {q₀, q₁}
δ(q₀, b) = {q₀}
δ(q₁, b) = {q₂}

Equivalent DFA (subset construction):
States become combinations:
{q₀}, {q₁}, {q₂}, {q₀,q₁}, {q₀,q₂}, {q₁,q₂}, {q₀,q₁,q₂}

δ'({q₀}, a) = {q₀, q₁}
δ'({q₀}, b) = {q₀}
δ'({q₀,q₁}, a) = {q₀, q₁}
δ'({q₀,q₁}, b) = {q₀, q₂}
...

Power Equivalence:

NFA ≡ DFA (Equal computational power)

Theorem: For every NFA, there exists an equivalent DFA
Conversion: Subset construction algorithm
Result: DFA may have up to 2^n states for n-state NFA

Advantages of NFA:

1. Easier to design for complex patterns
2. More intuitive representation
3. Fewer states needed
4. Better for theoretical analysis
5. Good for pattern matching algorithms

Disadvantages of NFA:

1. Slower execution (must track multiple paths)
2. Implementation more complex
3. Requires backtracking or parallel simulation
4. Not directly executable by hardware