Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Computer Engineering

Theory of Computation

Finite automata, regular expressions, grammars, PDAs, Turing machines, P and NP.

Interview questions
Your progress in this subject0 of 27 · 0%
  1. 1Formal languages and operations on languagesFormal languages are sets of strings over an alphabet; this note defines basic terms and operations (union, concatenation, Kleene star, complement, reversal, homomorphism, quotients, etc.), gives exact algebraic identities and closure properties (especially for regular and context-free languages), s
  2. 2Deterministic finite automataDeterministic finite automata (DFA) are simple state machines that recognise regular languages; they are used in lexical analysis, pattern matching and protocol design.
  3. 3Nondeterministic finite automata and NFA to DFA conversionNondeterministic finite automata (NFA) are finite-state machines where a symbol can lead to many possible next states; every NFA can be converted to an equivalent deterministic finite automaton (DFA) by the subset-construction algorithm.
  4. 4Epsilon-NFA and its conversionHow epsilon-NFAs (ε-NFAs) work and how to convert them to equivalent NFAs and DFAs using ε-closure and subset construction.
  5. 5Minimisation of DFAMinimisation of a DFA means producing the smallest deterministic finite automaton that recognises the same regular language; it is done by removing unreachable states and merging equivalent states using partition refinement (Moore or Hopcroft) and is unique up to isomorphism.
  6. 6Moore and Mealy machinesMoore and Mealy machines are two kinds of finite-state machines that produce outputs: Moore outputs depend only on states, Mealy outputs depend on state and input; they are equivalent in expressive power but differ in where outputs are produced and in practical state counts.
  7. 7Regular expressionsConcise study notes on regular expressions: definitions, algebra, conversion to/from finite automata, key theorems (Kleene, Arden), common patterns and exam-style worked examples.
  8. 8Conversions between regular expressions and finite automataHow to convert between regular expressions and finite automata (NFA/DFA): constructions, correctness ideas, and worked examples (Thompson, GNFA/state-elimination, Arden).
  9. 9Arden's theoremArden's theorem gives a method to solve simple linear equations over regular expressions (languages): the equation X = A X ∪ B has solution X = A* B, unique when A does not contain ε, and this is widely used to convert finite automata to regular expressions.
  10. 10Pumping lemma for regular languagesPumping lemma for regular languages gives a necessary property of every regular language and is used to prove some languages are not regular.
  11. 11Closure and decision properties of regular languagesClosure properties say which operations on languages keep regularity; decision properties say which questions about regular languages are algorithmically solvable and how to decide them.
  12. 12Myhill–Nerode theoremMyhill–Nerode theorem characterises regular languages by a right-invariant equivalence relation: a language is regular iff that relation has finitely many equivalence classes, and these classes give the states of the unique minimal DFA.
  13. 13Context-free grammars and derivationsContext-free grammars (CFGs) define programming-language-like structures using productions; understanding formal definitions, derivations (leftmost/rightmost), and parse trees is essential for parsing, compiler front-ends and designing pushdown automata.
  14. 14Ambiguous grammarsNotes on ambiguous grammars: what ambiguity means in context-free grammars, how to detect and remove it, examples (including inherently ambiguous languages), and exam-focused tips.
  15. 15Simplification of CFGsHow to simplify a context-free grammar by removing useless symbols, ε-productions, and unit productions while preserving the language (up to ε), with exact algorithms and worked examples.
  16. 16Pumping lemma for context-free languagesPumping lemma for context-free languages: a necessary property used to prove some languages are not context-free, derived from parse trees of grammars in Chomsky normal form.
  17. 17Chomsky hierarchy and applications of CFGsChomsky hierarchy classifies grammars and languages (Type-0 to Type-3) and shows where context-free grammars (CFGs) sit and how CFGs are used (parsing, compilers, PDAs).
  18. 18Pushdown automataPushdown automata (PDA): machines with a stack that accept exactly the context-free languages; definitions, constructions between CFG and PDA, examples, traces, and exam tips.
  19. 19PDA acceptance: final state and empty stackCompare and convert the two standard ways a pushdown automaton (PDA) can accept input: by empty stack and by final state; show formal definitions, constructions to convert one form to the other (for nondeterministic PDAs), worked examples, common mistakes and exam guidance.
  20. 20Equivalence of PDA and CFGEquivalence theorem: a language is context-free iff some pushdown automaton recognizes it, with constructive conversions both ways (CFG → PDA and PDA → CFG).
  21. 21Post machinesPost machines are a simple, Turing-equivalent model of computation (Emil Post) that uses a tape and a small set of instruction types to study computability and reductions.
  22. 22Turing machinesClear, exam-focused notes on Turing machines: definitions, formalism, design techniques, key theorems (undecidability of A_TM), worked constructions and traces, common mistakes, and exam guidance.
  23. 23Designing Turing machinesDesigning Turing machines: formal definition, design strategies, standard constructions (multi-tape simulation, nondeterminism), worked designs for a^n b^n and palindrome, common exam pitfalls and quick checks.
  24. 24Universal Turing machine and the Church–Turing thesisUniversal Turing machine (UTM) is a single Turing machine that can simulate any other Turing machine given its description; the Church–Turing thesis states that the intuitive notion of 'effectively calculable' equals 'computable by a Turing machine'.
  25. 25Decidability and the halting problemDecidability studies which problems (languages) a Turing machine can always answer correctly; the halting problem is the classic undecidable example showing limits of algorithmic computation.
  26. 26ReducibilityReducibility is the formal method of transforming one decision problem into another to compare their computability and recognizability; the main types are mapping (many-one) reducibility and Turing (oracle) reducibility and they are used to prove undecidability and completeness results.
  27. 27P, NP and NP-completenessDefinitions and key theorems about P, NP, NP-hard and NP-complete, how to show membership in NP, and a standard polynomial-time reduction (3-SAT to CLIQUE) with worked exam-style answers.

Coming next in Theory of Computation

  1. Chomsky and Greibach normal forms· notes coming
  2. Regular grammars and their equivalence with FA· notes coming
  3. Deterministic and nondeterministic PDA· notes coming
  4. Variants of Turing machines· notes coming
  5. Recursive and recursively enumerable languages· notes coming
  6. Rice's theorem· notes coming
  7. Post correspondence problem· notes coming
  8. Context-sensitive languages and linear bounded automata· notes coming
  9. Primitive recursive and μ-recursive functions· notes coming
  10. Left recursion and left factoring· notes coming