Deterministic Finite Automata ( DFA ) Bangla। Compiler Design । Lecture 1

This is the first video of the new video series (Compiler Design).In DFA, for each input symbol, one can determine the state to which the machine will move. Hence, it is called Deterministic Automaton. As it has a finite number of states, the machine is called Deterministic Finite Machine or Deterministic Finite Automaton.

Notes on the definition :-
The set Q in the above definition is simply a set with a finite number of elements. Its elements can, however, be interpreted as a state that the system (automaton) is in. Thus in the example of vending machine, for example, the states of the machine such as "waiting for a customer to put a coin in", "have received 5 cents" etc. are the elements of Q. "Waiting for a customer to put a coin in" can be considered the initial state of this automaton and the state in which the machine gives out a soda can can be considered the accepting state.
The transition function is also called a next state function meaning that the automaton moves into the state (q, a) if it receives the input symbol a while in state q.
Thus in the example of vending machine, if q is the initial state and a nickel is put in, then (q, a) is equal to "have received 5 cents".
Note that is a function. Thus for each state q of Q and for each symbol a of , (q, a) must be specified.
The accepting states are used to distinguish sequences of inputs given to the finite automaton. If the finite automaton is in an accepting state when the input ceases to come, the sequence of input symbols given to the finite automaton is "accepted". Otherwise it is not accepted. For example, in the Example 1 below, the string a is accepted by the finite automaton. But any other strings such as aa, aaa, etc. are not accepted.
A deterministic finite automaton is also called simply a "finite automaton". Abbreviations such as FA and DFA are used to denote deterministic finite automaton.