1. Finite Automata & Regular Languages
A DFA (Deterministic Finite Automaton) has exactly one transition per symbol per state; an NFA (Non-deterministic Finite Automaton) may have zero, one or multiple transitions for a symbol, plus optional ε-transitions (moves with no input consumed). A key theorem: NFAs and DFAs recognise exactly the same class of languages — regular languages — despite NFAs looking more powerful; every NFA can be converted to an equivalent DFA (the subset construction), though possibly with exponentially more states.
Regular languages are exactly the languages describable by a regular expression, and are closed under union, concatenation, Kleene star, intersection and complement. The pumping lemma for regular languages is the standard tool for proving a language is NOT regular: it states that any sufficiently long string in a regular language can be split into three parts where the middle part can be repeated any number of times and the result still belongs to the language — a language like {aⁿbⁿ : n ≥ 0} fails this (you can't "pump" the a's without breaking the a-count = b-count requirement), proving it's not regular.
States: {q_even, q_odd} (q_even is both start and accepting state)
Transition table:
State on '0' on '1'
q_even q_even q_odd
q_odd q_odd q_even
Trace on input "1011":
start q_even -1-> q_odd -0-> q_odd -1-> q_even -1-> q_odd
Final state q_odd is NOT accepting -> "1011" is REJECTED
(it has three 1s, which is odd -- correctly rejected)NFA and DFA recognise the SAME language class (regular languages) — an NFA is never more powerful in terms of what it can recognise, only potentially more compact to describe. Don't confuse "non-deterministic" with "more powerful."
2. Context-Free Grammars, Pushdown Automata & Turing Machines
A Context-Free Grammar (CFG) has production rules of the form A → α where A is a single non-terminal (unlike regular grammars, which are more restricted). CFGs generate context-free languages, recognised exactly by Pushdown Automata (PDA) — a finite automaton augmented with a stack, which is precisely the extra memory needed to handle unbounded nesting/matching (like balanced parentheses or {aⁿbⁿ}), something a plain finite automaton with no memory cannot do.
A Turing Machine (TM) extends this further with an infinite tape it can read, write and move along in both directions — it is the most powerful model in the standard hierarchy, capable of recognising the recursively enumerable languages (and, if guaranteed to always halt, the recursive/decidable languages). The Chomsky hierarchy nests these four classes strictly: regular ⊂ context-free ⊂ context-sensitive ⊂ recursively enumerable, with DFA/NFA, PDA, linear-bounded automaton, and TM as their respective recognising machines.
Type 3: Regular languages <-> Finite Automaton (DFA/NFA)
Type 2: Context-free languages <-> Pushdown Automaton (PDA)
Type 1: Context-sensitive languages<-> Linear-Bounded Automaton
Type 0: Recursively enumerable <-> Turing Machine
Each class strictly CONTAINS the one above it:
Regular (subset of) Context-free (subset of) Context-sensitive (subset of) Rec. Enumerable3. Compiler Phases
A compiler translates source code to target code across a fixed sequence of phases: Lexical analysis (scanner) groups characters into tokens (identifiers, keywords, operators), discarding whitespace/comments — implemented using exactly the finite-automaton theory from this week. Syntax analysis (parser) checks the token stream against the language's grammar (a CFG) and builds a parse tree/AST — top-down (LL) or bottom-up (LR) parsing are the two families. Semantic analysis checks meaning-level rules a grammar can't express, like type checking and scope resolution.
After semantic analysis: Intermediate code generation produces a machine-independent representation (e.g. three-address code); Code optimization improves this intermediate code without changing its meaning (common subexpression elimination, dead code removal); and Code generation produces the final target machine code. A symbol table is built and consulted throughout every phase, tracking identifiers, their types, and their scope.
This is not a coincidence of naming: lexical analysis is literally implemented as a DFA recognising each token type as a regular language, and syntax analysis is literally a PDA-style algorithm parsing against a CFG — the theory earlier in this week is the direct engineering foundation of the first two compiler phases.
4. Hands-on Exercise
Build a DFA, and trace a string through a compiler's first two phases
This unit rewards small, complete constructions over passive reading of definitions.
Part 1 — Automata:
- Design a DFA over {a,b} that accepts exactly the strings ending in "ab".
- Trace your DFA on the input "aabab" state by state and confirm whether it accepts or rejects.
- Explain in one sentence why a plain DFA (no stack) cannot recognise {aⁿbⁿ : n ≥ 0}.
Part 2 — Compiler phases:
- Take the tiny statement `int total = a + b * 2;` and list the tokens lexical analysis would produce.
- Sketch the shape of the parse tree/AST that syntax analysis would build for the expression `a + b * 2` (showing that * binds tighter than +).
- Name one specific semantic error this line could contain that lexical and syntax analysis alone would NOT catch (hint: think about types).
5. Exam-Style Practice (UGC NET Pattern)
Five NTA-pattern questions on automata theory and compiler phases.
Q1
Which of the following statements about NFAs and DFAs is correct?
A) NFAs can recognise a strictly larger class of languages than DFAs
B) NFAs and DFAs recognise exactly the same class of languages (regular languages)
C) DFAs can recognise context-free languages that NFAs cannot
D) NFAs cannot be converted to an equivalent DFA
Which of the following statements about NFAs and DFAs is correct?
A) NFAs can recognise a strictly larger class of languages than DFAs
B) NFAs and DFAs recognise exactly the same class of languages (regular languages)
C) DFAs can recognise context-free languages that NFAs cannot
D) NFAs cannot be converted to an equivalent DFA
Correct answer: B) NFAs and DFAs recognise exactly the same class of languages (regular languages). Despite appearing more powerful, NFAs recognise exactly the regular languages — the same class DFAs recognise — and every NFA can be converted to an equivalent DFA via the subset construction.
Q2
Which automaton is exactly equivalent in power to context-free grammars — i.e. it recognises precisely the context-free languages?
A) Deterministic Finite Automaton
B) Pushdown Automaton
C) Linear-Bounded Automaton
D) Turing Machine
Which automaton is exactly equivalent in power to context-free grammars — i.e. it recognises precisely the context-free languages?
A) Deterministic Finite Automaton
B) Pushdown Automaton
C) Linear-Bounded Automaton
D) Turing Machine
Correct answer: B) Pushdown Automaton. A Pushdown Automaton (a finite automaton augmented with a stack) recognises exactly the context-free languages, matching context-free grammars in generative power.
Q3
The language {aⁿbⁿ : n ≥ 0} is a standard example used to show that regular languages cannot express:
A) Concatenation of two strings
B) Unbounded counting/matching between two symbols
C) The empty string
D) Union of two languages
The language {aⁿbⁿ : n ≥ 0} is a standard example used to show that regular languages cannot express:
A) Concatenation of two strings
B) Unbounded counting/matching between two symbols
C) The empty string
D) Union of two languages
Correct answer: B) Unbounded counting/matching between two symbols. This language requires matching an unbounded, equal count of a's and b's — something a finite automaton with no memory cannot track for arbitrarily large n, which is exactly what the pumping lemma is used to prove.
Q4
Which compiler phase is directly responsible for grouping characters of the source code into tokens such as identifiers, keywords and operators?
A) Syntax analysis
B) Lexical analysis
C) Semantic analysis
D) Code generation
Which compiler phase is directly responsible for grouping characters of the source code into tokens such as identifiers, keywords and operators?
A) Syntax analysis
B) Lexical analysis
C) Semantic analysis
D) Code generation
Correct answer: B) Lexical analysis. Lexical analysis (performed by the scanner) is the phase that groups raw characters into tokens, discarding whitespace and comments, before syntax analysis works on the resulting token stream.
Q5
Which compiler phase would detect that an expression tries to add an integer to a string, given that both are syntactically valid operands?
A) Lexical analysis
B) Syntax analysis
C) Semantic analysis
D) Code optimization
Which compiler phase would detect that an expression tries to add an integer to a string, given that both are syntactically valid operands?
A) Lexical analysis
B) Syntax analysis
C) Semantic analysis
D) Code optimization
Correct answer: C) Semantic analysis. Type mismatches are a meaning-level (semantic) rule, not a grammar (syntax) rule — the expression can be perfectly well-formed syntactically while still being semantically invalid, which is exactly what semantic analysis (including type checking) catches.