This subject is two halves of one story. Automata theory asks what simple machines can compute and what languages they recognise. Compiler design applies that theory to build the programs that turn source code into running software. Regular expressions, config parsers, linters, Dockerfile and YAML parsers, and every programming language you use depend on it. This article revisits the five units of the JNTUK course.
Unit 1: Finite automata and regular languages
Basic terms
| Term | Meaning |
|---|---|
| Alphabet Σ | A finite set of symbols (for example {0, 1}) |
| String | A finite sequence of symbols; ε is the empty string |
| Language | A set of strings over an alphabet |
| Σ* | All possible strings |
Finite automata
A finite automaton reads input one symbol at a time and moves between states. Formally it is a 5-tuple (Q, Σ, δ, q₀, F): states, alphabet, transition function, start state and accepting states.
| Type | Behaviour |
|---|---|
| DFA (deterministic) | Exactly one move for each state and symbol |
| NFA (non-deterministic) | May have several moves, or none, for a state and symbol |
| ε-NFA | Can also move without reading input |
Every NFA can be converted to an equivalent DFA by subset construction, so they recognise the same class of languages, the regular languages, though the DFA may have exponentially more states. A DFA can be minimised by merging indistinguishable states.
Regular expressions and limits
A regular expression uses union (|), concatenation and the Kleene star (*). Regular expressions and finite automata are equivalent, and Kleene’s theorem and Arden’s theorem convert one to the other. Moore and Mealy machines are automata with output. Regular languages are closed under union, intersection, complement and concatenation.
The pumping lemma proves a language is not regular. For example, {0ⁿ1ⁿ} is not regular, because a finite automaton cannot count without limit.
Today: regular expressions in
grep,sed, Python’sre, log filters and WAF rules are compiled to automata. Protocol state machines, TCP connection states and UI flows are finite automata too.
Unit 2: Context-free grammars and pushdown automata
Context-free grammars (CFG)
A grammar has terminals, non-terminals, production rules and a start symbol. A CFG has rules with a single non-terminal on the left, such as E → E + E | id. This can describe nesting, such as balanced brackets, which regular expressions cannot.
| Idea | Meaning |
|---|---|
| Derivation | Applying rules from the start symbol to a string; leftmost or rightmost |
| Parse tree | The tree form of a derivation |
| Ambiguity | A string with more than one parse tree; the grammar must be rewritten (set precedence and associativity) |
| Simplification | Remove useless symbols, ε-rules and unit rules |
| Normal forms | Chomsky (A → BC or A → a) and Greibach (A → aα) |
Pushdown automata (PDA)
A PDA is a finite automaton plus a stack. It accepts exactly the context-free languages. The stack lets it remember, for example, how many opening brackets are still unmatched. A language like {0ⁿ1ⁿ} is context-free but not regular. Another pumping lemma proves a language is not context-free.
The Chomsky hierarchy
| Type | Grammar | Machine | Example use |
|---|---|---|---|
| 3 | Regular | Finite automaton | Tokens, simple patterns |
| 2 | Context-free | Pushdown automaton | Programming language syntax |
| 1 | Context-sensitive | Linear-bounded automaton | Some natural-language rules |
| 0 | Unrestricted | Turing machine | Anything computable |
Today: JSON, XML, YAML and programming language syntax are described by context-free grammars. Their parsers use a stack, explicitly or through recursion, to handle nesting.
Unit 3: Turing machines and computability
A Turing machine has an infinite tape, a head that reads, writes and moves left or right, and a finite set of states. Despite its simplicity it can compute anything that any computer can; the Church-Turing thesis states that “computable” means “computable by a Turing machine”. Variants (multi-tape, non-deterministic) are no more powerful.
| Concept | Meaning |
|---|---|
| Recursive (decidable) language | A Turing machine always halts with yes or no |
| Recursively enumerable language | The machine accepts members but may run forever on non-members |
| Universal Turing machine | A machine that simulates any other; the idea of a stored-program computer |
| Halting problem | Deciding whether a program halts is undecidable: no algorithm works for all programs |
| Reduction | Show a new problem is undecidable by reducing a known one to it |
Related ideas include Post’s Correspondence Problem and Rice’s theorem (any non-trivial property of what a program computes is undecidable). The complexity classes P, NP and NP-complete place problems by how costly they are.
Today: the halting problem is why no tool can perfectly detect all infinite loops, all bugs or all malware. Static analysers and linters therefore approximate, and they sometimes give false positives or miss bugs.
Unit 4: Lexical and syntax analysis
Compiler structure
A compiler turns source code into target code in phases.
| Phase | Input and output |
|---|---|
| Lexical analysis | Characters to tokens (keywords, identifiers, numbers, operators) |
| Syntax analysis (parsing) | Tokens to a parse tree or syntax tree |
| Semantic analysis | Checks types and scope |
| Intermediate code generation | A machine-independent form, such as three-address code |
| Optimization | Faster or smaller code |
| Code generation | Target machine code |
The symbol table stores names and their information; the error handler serves all phases. A front end (analysis) is separate from a back end (synthesis). Tools include cross-compilers, interpreters and bootstrapping.
Lexical analysis
The lexer (scanner) removes whitespace and comments and groups characters into tokens using regular expressions, implemented as a DFA. Lex/Flex generate lexers from a list of patterns.
Parsing
| Parser | Direction | Notes |
|---|---|---|
| Recursive descent / LL(1) | Top-down, reads left to right, leftmost derivation | Needs FIRST and FOLLOW sets; no left recursion, no common prefixes |
| Shift-reduce | Bottom-up | Uses a stack: shift the next token, reduce by a rule |
| LR(0), SLR(1), LALR(1), CLR(1) | Bottom-up, increasing power | Built from item sets and parse tables; LALR(1) is used by Yacc/Bison |
| Operator precedence | Bottom-up | For expression grammars |
Bottom-up LR parsers handle a larger class of grammars than LL parsers. Conflicts (shift-reduce, reduce-reduce) show a grammar problem.
Today: every language tool uses a lexer and parser:
gcc, the Python interpreter,jq, an HCL parser for Terraform, an editor’s syntax highlighter and your IDE’s error underlines. Modern tools such as ANTLR and tree-sitter generate parsers from grammars.
Unit 5: Semantic analysis, code generation and optimization
Syntax-directed translation
A syntax-directed definition attaches attributes and rules to grammar productions, to compute types and values while parsing. Attributes are synthesized (computed from children) or inherited (passed from parent or siblings).
Semantic analysis and intermediate code
- Type checking: make sure operands match operators and calls match function declarations; type conversion and coercion.
- Scope and symbol table: which declaration a name refers to.
- Run-time environments: activation records on the stack, parameter passing (by value, by reference), the heap and garbage collection.
- Intermediate representations: syntax tree, three-address code (
t1 = a + b), quadruples and triples, static single assignment (SSA).
Optimization
| Technique | Idea |
|---|---|
| Constant folding | Compute 2 * 3 at compile time |
| Common sub-expression elimination | Compute a repeated expression once |
| Dead-code elimination | Remove code whose result is never used |
| Loop optimization | Code motion out of loops, strength reduction, induction variables |
| Inlining | Replace a call with the function body |
| Peephole optimization | Improve small windows of target code |
Optimization uses basic blocks, control-flow graphs and data-flow analysis.
Code generation
Chooses instructions, allocates registers (modelled as graph colouring) and orders the code. Issues include the target architecture, instruction selection and addressing modes.
Today: LLVM, GCC and the JVM’s JIT compiler perform these steps, and the same “front end, intermediate representation, back end” design lets one compiler support many languages and many CPUs. The Go, Rust and Java toolchains you meet in builds are compilers, and a Docker multi-stage build is often just a compile step.
One-minute recap
| Unit | Key idea | You meet it in |
|---|---|---|
| 1. Finite automata | DFA, NFA, regular expressions, pumping lemma | grep, log filters, protocol state machines |
| 2. CFG and PDA | Grammars, ambiguity, stack-based recognition, Chomsky hierarchy | JSON, YAML and language syntax |
| 3. Turing machines | Computability, halting problem, undecidability | Limits of static analysers and malware detection |
| 4. Lexing and parsing | Tokens by regex, LL and LR parsers | Compilers, IDEs, Terraform and config parsers |
| 5. Semantics and codegen | Type checking, three-address code, optimization, registers | LLVM, GCC, JIT compilers |
Next in Engineering Revisited: Computer Networks.
Written by Claude, Anthropic’s AI assistant, as part of Engineering Revisited, a quick refresher of the B.Tech subjects one at a time.