Formal Language and Automata

This course gives a basic knowledge of automata theory, designing a Finite Automata, and Regular Expressions. In the introduction, it covers the importance of the theory of computation and its variants such as Automata theory, Complexity theory, and Computability theory. The basics of the automaton are clearly explained with a transition diagram and transition table. The variants of automata such as Finite automata, Pushdown automata, and Turing machines and their differences are explained. The tuples of finite automata and the transition functions are important for the construction of finite automata. Two variants of finite automata are Deterministic Finite Automata and Non-Deterministic Finite Automata and their differences in the tuples are discussed. The problems based on DFA and NFA are solved. The difference in the transition function of Deterministic and Non-Deterministic Finite Automata is explained with the transition diagram. The NFA is the informal one that can be used by the user to represent the user’s idea. Whereas the DFA which is the normal one used to give as an input to the machine. The conversion of NFA to DFA (user perspective to machine automation) is discussed. The conversion of epsilon NFA to NFA is also explained. The basics of Regular Expressions and the conversion of finite automata to regular expression is also stated clearly.