Unit-1 introduces Finite Automata (FA) or Finite State Machines (FSM) with the languages they process; these languages are called regular languages. Every regular language is defined by a regular expression. Unit-1 defines Deterministic Finite Automata (DFA) and Non-deterministic Finite Automata (NFA). It also examines properties of regular languages which are processed by DFA and NFA. Regular languages are the simplest subset of recursively enumerable languages. The relationship of regular languages with other languages is shown in the Chomsky Hierarchy. Important topics for this unit are: [1a] Introduction,     [1b] Finite Automata,    [1c] Regular Languages,    [1d] Regular Languages in MS Word format,     [1e] Animation of a Finite Automaton.

This tutorial on Mathematical Foundations or the Theory of Computation presented in this unit and others are mainly based on Hopcroft, J., Motwani, R. & Ullman, J. (2007), Introduction to Automata Theory, Languages, and Computation, 3rd Edition, Addison Wesley and Daniel Cohen, (1997), Introduction to Computer Theory, 2nd Edition, John Wiley & Sons, and Sipser, M. (2012) Introduction to the Theory of Computation, Cengage Learning, 3rd edition. Revealing examples are taken from these sources in order to explain mathematical models of computation.     Please click here to go back to the Mathematical Foundations home page .