IT-503 (A) Theory of Computation Notes
5 notes for Theory of Computation, unit by unit.
Notes for IT-503 (A)
- Unit 1 · Short notes Finite State Automata Introduction to the theory of computation · Description of finite automata · Properties of transition functions · Transition graph design · Designing finite automata (FSM) · Deterministic Finite Automaton (DFA)
- Unit 2 · Short notes Regular Languages and Expressions Regular grammars · Regular expressions · Regular sets · Closure properties of regular grammars · Arden’s theorem · Myhill‑Nerode theorem
- Unit 3 · Short notes Context‑Free Grammars Introduction to context‑free grammar (CFG) · Derivation (parse) trees · Ambiguity in CFGs · Simplification of CFGs · Chomsky Normal Form (CNF) · Greibach Normal Form (GNF)
- Unit 4 · Short notes Pushdown Automata Introduction to pushdown automata (PDA) · Formal definition of PDA · Closure properties of PDA · Examples of PDA · Deterministic pushdown automata (DPDA) · Nondeterministic pushdown automata (NPDA)
- Unit 5 · Short notes Turing Machines and Complexity Basics and formal definition of Turing machines (TM) · Language acceptability by TM · Examples of Turing machines · Multitape Turing machines · Nondeterministic Turing machines (NDTM) · Universal Turing machine
More for IT-503 (A)
Other 5th semester IT subjects
- IT-501 Operating System
- IT-502 Computer Networks
- IT-503 (B) Microprocessor and Interfacing
- IT-503 (C) Object Oriented Analysis and Design
- IT-504 (A) Artificial Intelligence
- IT-504 (B) E Commerce & Governance
- IT-504 (C) Java Programming
- IT-505 Advanced Java Lab