Basic Foundations
Review of set theory, logic, functions, proofs; Automata, computability, and complexity; Basic concepts of formal languages.
Theory of Computation Chapters
B.Sc. CSIT - Fourth Semester
Introduction to Finite Automata
Finite automata and finite state machines; Deterministic finite automata (DFA); Notations; Language of DFA; Extended transition functions.
Regular Expression
Regular expressions; Regular operators; Regular languages; Algebraic rules; Equivalence of regular expressions and finite automata.
Context Free Grammar
Components of CFG; Context-free languages; Derivations; Leftmost and rightmost derivations; Parse trees; Ambiguity.
Push Down Automata
Introduction to PDA; Representation; Operations; Moves; Instantaneous description; Deterministic and nondeterministic PDAs.
Turing Machine
Introduction; Notations; Language of a Turing Machine; ID of TM; Acceptance; Variants of TM.
Undecidability and Intractability
Computational complexity; Time & space complexity; Intractability; Complexity classes; Types of problems.