CS-501 Theory of Computation Notes
5 notes for Theory of Computation, unit by unit.
Notes for CS-501
- Unit 1 · Short notes Introduction of Automata Theory Examples of automata machines · Finite Automata as a language acceptor and translator · Moore machines and Mealy machines · Composite machine · Conversion from Mealy to Moore and vice versa
- Unit 2 · Short notes Types of Finite Automata Non‑Deterministic Finite Automata (NDFA) · Deterministic Finite Automata (DFA) · Conversion of NDFA to DFA · Minimization of automata machines · Regular expressions and Arden’s theorem · Union, intersection, concatenation and closure; 2‑way DFA
- Unit 3 · Short notes Grammars Types of grammar: context‑sensitive, context‑free, regular · Derivation trees, ambiguity, simplification of context‑free grammar, conversion of grammar to automata and vice versa · Chomsky hierarchy, killing null and unit productions · Chomsky normal form and Greibach normal form
- Unit 4 · Short notes Push‑down Automata Examples of PDA, deterministic and non‑deterministic PDA · Conversion of PDA into context‑free grammar and vice versa · CFG equivalent to PDA · Petri‑net model
- Unit 5 · Short notes Turing Machine Techniques for construction; Universal Turing machine, multitape, multi‑head and multidimensional Turing machines, NP‑complete problems · Decidability and recursively enumerable languages; decidable, undecidable languages, halting problem, Post correspondence problem
More for CS-501
Other 5th semester CSE subjects
- CS-502 Database Management Systems
- CS-503 (A) Data Analytics
- CS-503 (B) Pattern Recognition
- CS-503 (C) Cyber Security
- CS-504 (A) Internet and Web Technology
- CS-504 (B) Object Oriented Programming
- CS-504 (C) Introduction to Database Management Systems
- CS-505 Linux (LAB)
- CS-506 Python