# CSE501 / TOC ## Syllabus {% file src="" %} ## Resources

MI: Finite Automata and Regular Languages

* Introduction * Basic mathematical notation and techniques * Finite state systems and basic definitions * Finite automata models * Deterministic finite automaton (DFA) * Nondeterministic finite automaton (NDFA/NFA) * Finite automaton with ε\varepsilonε-moves * Regular languages and expressions * Regular languages * Regular expressions * Equivalence of NFA and DFA * Equivalence of NFA with and without ε\varepsilonε-moves * Equivalence of finite automata and regular expressions * DFA minimization * Minimization techniques for DFA * Pumping lemma for regular sets * Statement of pumping lemma * Problems based on pumping lemma ***

[⤓]	Content Preview
	Session-1+2
	Session-3+4
	Session-5
	Session-6
	Session-7
	Session-8
	Session-9
	Session-10
	Session-11+12

MII: Grammars

* Introduction to grammars * Basic concepts of grammars * Types of grammars * Context-free grammars (CFG) and languages * Definitions of CFG and CFL * Derivations and generated languages * Ambiguity in grammars * Relationship between derivations and derivation trees * Simplification of CFG * Elimination of useless symbols * Elimination of unit productions * Elimination of null productions * Normal forms * Greibach Normal Form (GNF) * Chomsky Normal Form (CNF) * Problems related to CNF and GNF * Chomsky hierarchy * Chomsky hierarchy of languages ***

[⤓]	Content Preview
	Session-1
	Session-2
	Session-3+4
	Session-5+6
	Session-7+8
	Session-9
	Session-10

MIII: Pushdown Automata and Linear Bounded Automata

* Pushdown automata (PDA) * Definitions and basic components * Moves and instantaneous descriptions * Deterministic pushdown automata (DPDA) * PDA and CFL * Equivalence of PDA and context-free languages * Pumping lemma for CFL * Statement of pumping lemma for CFL * Problems based on pumping lemma * Linear bounded automata (LBA) * Definition and basic idea ***

[⤓]	Content Preview
	Session-1+2
	Session-3
	Session-4
	Session-5
	Session-6

MIV: Turing Machines

* Turing machine model * Basic model and components * Language acceptability of Turing machines * Design of Turing machines * Construction for simple languages and functions * Variants of Turing machines * Variations of TM * Universal Turing machine * Church’s machine (Church–Turing thesis context) * Undecidability examples * Turing machine halting problem * Post correspondence problem (PCP) * Modified PCP ***

[⤓]	Content Preview
	Session-1+2
	Session-3
	Session-4
	Session-5

MV: Unsolvable Problems and Computable Functions

* Computable functions * Primitive recursive functions * Recursive and recursively enumerable languages * Unsolvable problems * Examples of unsolvable problems * Tractability and intractability * Tractable vs. intractable problems * Class P and class NP problems * NP-completeness * Satisfiability problem (SAT) ***

[⤓]	Content Preview
	Session-1
	Session-2

## Notes ## Question Directory ### Previous Year Questions #### Mid-Sem-PYQ

[⤓]	Content Preview
	Y3S5-CSE501-TOC-MidTerm-PYQ-OCT25

#### End-Sem-PYQ

[⤓]	Content Preview
	Y3S5-CSE501-TOC-EndSem-PYQ-APR17
	Y3S5-CSE501-TOC-EndSem-PYQ-APR18
	Y3S5-CSE501-TOC-EndSem-PYQ-APR19
	Y3S5-CSE501-TOC-EndSem-PYQ-JAN23
	Y3S5-CSE501-TOC-EndSem-PYQ-DEC23

## External Sources {% embed url="" %} *** {% embed url="" %} {% embed url="" %} {% embed url="" %}