Syllabus
Every topic below links to the page that teaches it, and a test walks this list on every build: a topic pointing at a route that does not exist fails CI. So nothing here is an aspiration.
The syllabus is data rather than code — one shared topic graph, one file per institution. The two schemes below have identical section lists, which is why the second costs almost nothing to carry.
42 lecture hours, no tutorial hours, and 56 self-study hours. More than half of a student’s time with this subject is unsupervised — which is the gap every trace in this app exists to fill.
Module 1 — Finite automata
- Alphabets, strings and languages Alphabets, powers, Σ*, length and concatenation, with every string of length ≤ k listed.
- Deterministic finite automata Run a DFA, NFA or ε-NFA on an input and watch every step, branch and ε-closure.
- Nondeterministic finite automata Run a DFA, NFA or ε-NFA on an input and watch every step, branch and ε-closure.
- ε-NFAs and ε-closure Run a DFA, NFA or ε-NFA on an input and watch every step, branch and ε-closure.
- The subset construction Watch the subset construction build each state, one reachable subset at a time.
- Text search Keywords to a guessing NFA to a recognising DFA, scanning real text with overlapping matches.
Module 2 — Regular expressions and languages
- Regular expressions Thompson construction from a regular expression, and state elimination back again.
- RE to ε-NFA (Thompson) Thompson construction from a regular expression, and state elimination back again.
- DFA to RE (state elimination)
- The pumping lemma Play the adversary, or watch it play you, on a language that is not regular.
- Closure properties of regular languages Union, intersection, complement, difference, reversal and homomorphisms — each built step by step.
- DFA minimisation Table filling and partition refinement, with the distinguishable pairs marked as they are found.
Module 3 — Context-free grammars and pushdown automata
- Context-free grammars Derivations with growing parse trees, the ambiguity detector, and left recursion elimination.
- Derivations and parse trees Derivations with growing parse trees, the ambiguity detector, and left recursion elimination.
- Ambiguity
- Left recursion elimination
- Pushdown automata Run a PDA with state, input and stack in sync, the branch tree for every guess, and the ID sequence written out.
- Final state and empty stack Final state to empty stack and back, with the bottom marker doing the work.
- Equivalence of PDAs and CFGs The one-state construction of Theorem 6.13, then the built machine run on real inputs.
- Deterministic PDAs Type δ line by line, see the machine drawn with a, X/YX labels, and check whether it is deterministic — pair by overlapping pair.
Module 4 — Properties of context-free languages
- Grammar simplification ε-productions, unit productions, useless symbols and Chomsky Normal Form as one pipeline in the safe order, the grammar diffed at each stage.
- Chomsky normal form ε-productions, unit productions, useless symbols and Chomsky Normal Form as one pipeline in the safe order, the grammar diffed at each stage.
- The pumping lemma for CFLs Play the adversary, or watch it play you, on a language that is not regular.
- Closure properties of CFLs Union, concatenation, closure, reversal, substitution, intersection with a regular language, inverse homomorphism — and the intersection that fails.
Module 5 — Turing machines and undecidability
- Problems computers cannot solve Recursive inside RE inside everything, the four places a language and its complement can sit, and what the two classes are closed under.
- Turing machines The chapter 8 machines run on a scrolling tape, the ID sequence written out, and a non-halting run stopped honestly.
- Programming techniques for TMs The chapter 8 machines run on a scrolling tape, the ID sequence written out, and a non-halting run stopped honestly.
- Multitape and nondeterministic TMs Theorem 8.9 animated, with the 4n + 2k cost of Theorem 8.10 counted live.
- A language that is not recursively enumerable Fig. 9.1 with every cell computed: machines decoded from binary strings, run under a step budget, and a diagonal you can complement.
- Recursive languages and their complements Recursive inside RE inside everything, the four places a language and its complement can sit, and what the two classes are closed under.
- The universal language, and why it is undecidable Recursive inside RE inside everything, the four places a language and its complement can sit, and what the two classes are closed under.
- Reducing one problem to another Drop one problem onto another to build A ≤ B, with the construction and the contradiction drawn — and the wrong direction refused.
- Classifying a language Nested rings from regular out to every language, each with its machine, its closure and its pumping lemma, and the languages that separate them.
Course outcomes
- CO1 · Bloom level 2
- Explain the concepts of finite automata, regular languages, context-free languages and Turing machines
- CO2 · Bloom level 3
- Apply automata theory principles to construct FA, RE, CFG, PDA and their equivalent models
- CO3 · Bloom level 4
- Analyze formal languages and computational models to determine language properties, automata equivalence, closure properties
- CO4 · Bloom level 4
- Analyze CFGs, PDAs and TMs to solve computational problems and distinguish classes of formal languages
- CO5 · Bloom level 4
- Analyze decidability, undecidability and computability to classify problems by solvability
Tutorial components
The components the syllabus prescribes, and what delivers each. One is not built, and says so.
- Lexical analyzer design using regular expressions — Regular expressions
- Pattern matching and search engine simulation using finite automata — Text search
- Balanced parentheses checker using pushdown automata — Pushdown automata
- Syntax validation of simple programming statements using CFGs — Derivations and parse trees
- String processing problems using Turing machine concepts — Turing machines
- Language classification (regular, CFL, CSL, recursive, RE) — Classifying a language
- Automata simulation using the JFLAP tool — Not built. JFLAP’s .jff import is scheduled after v1.0, and until it exists nothing here delivers this component.
Where the source documents disagree
Recorded rather than quietly resolved. Worth one question to the course faculty before anything here is treated as settled.
- The lesson plan states 40 teaching hours; the syllabus document states 42. The syllabus is taken as authoritative.
- The lesson plan maps CO1 and CO2 across modules 1–4 and CO3 and CO4 across modules 3–4; the syllabus gives the clean one-to-one mapping shown here.
- The model question papers tag every sub-part CL2 or CL3, while the syllabus claims CL4 for CO3 to CO5.
- The departmental gap-analysis document still carries the older VTU code BCS503.
Deliberately out of scope
Five topics the published section list excludes, kept out rather than built and mislabelled: PDA → CFG and the [pXq] construction (6.3.2), CYK and the decision properties of CFLs (7.4), the R⁽ᵏ⁾ᵢⱼ construction for DFA → RE (3.2.1, which the syllabus excludes by name), the decision properties of regular languages (4.3), and the formal-proof sections (1.2, 1.4). Post’s Correspondence Problem and P versus NP are absent from the scheme entirely. They remain on the roadmap as enrichment, after v1.0.
Minimisation is not among them: it lives in 4.4, which is listed. Left recursion elimination is not in Hopcroft at all — it is a parsing topic — but it is examined at 8 marks, so it is built and carries no section citation.