Introduction to Automata, Languages and Computation

From deterministic machines to nondeterminism

This NPTEL course from IIT Kharagpur, with 62 lectures, begins with deterministic finite automata and how a DFA's input alphabet, transition function and language fit together. It then builds the same ideas for nondeterministic automata and shows why the two models accept the same languages.

The core sequence

• Building DFAs, worked through over several lectures.
• NFAs, their languages, and the subset construction that turns an NFA into a DFA.
• Epsilon-NFAs, including their extended transition function and their conversion to NFAs and DFAs.

Who it is for

Students meeting automata theory for the first time will find the progression clear, since each model is introduced as a refinement of the last. Anyone who already knows regular languages can use the epsilon-NFA lectures to fill in the conversion steps they may have skipped.