Regular Languages

In this part of the course we focus on studying Regular languages:

• we give 3 equivalent ways of describing regular languages:
  • as the languages described by regular expressions,
  • as the languages recognized by Deterministic Finite Automata (DFAs), and
  • as the languages recognized by Non-deterministic Finite Automata (\epsilon-NFAs).
• we show how to convert between these different descriptions;
• we show how to minimize DFAs;
• we show how to prove that a language is not regular.

Goals

At the end of this part of the course you should be able to:

• convert between regular expressions, DFAs, and \epsilon-NFAs;
• minimize DFAs;
• given a language, either use regular expressions/DFAs/\epsilon-NFAs to describe it or to prove that it is not regular.

References

The main reference for this part of the course is (Sipser 2013, chap. 1).

Sipser, Michael. 2013. Introduction to the Theory of Computation. 3rd ed. Cengage Learning.