Regular Languages

Formal definition

A regular language is a formal language for which there exists a deterministic finite automaton that accepts all and only those strings in the language.

Let’s look at a few examples of regular languages and their corresponding DFA.

DFA accepting strings starting with $a$ and ending with $b$

Consider the language $K$, of all strings that begin with an $a$ and end with a $b$. We can write this language as $K = \{ \textrm{all strings that begin with an }a \textrm{ and end with a } b \}$. If the first symbol is a $b$, then there is no hope of the machine accepting it. The following figure shows a machine that accepts all the strings starting with an $a$ and ending with a $b$.