UNIT – III - Finite Automata
UNIT – III - Finite Automata Syllabus: Finite Automata · DFA · NDFA · DFA vs NDFA · NFA to DFA Conversion · Minimization of DFA · Regular Expressions · Pumping Lemma · Myhill–Nerode Theorem TOPIC 1 Introduction to Finite Automata A Finite Automaton (FA) is an abstract mathematical machine that recognizes patterns in strings of symbols. It reads the input one symbol at a time and decides whether the string belongs to a particular language. It has a finite number of states and transitions between those states. Example: A machine that checks whether a binary number ends with 1 can be designed as a finite automaton. Important Terminology Term Definition Example State A condition or configuration of the machine q 0 , q 1 Input alphabet (Σ) A finite set of input symbols Σ = {0, 1} String A finite sequence of symbols from Σ ...