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$.

DFA accepting strings with a 1 in the next-to-last position

Consider the alphabet $\{0, 1\}$. How would we construct a DFA that accepts the language $L$, which contains strings of zeros and ones where the next-to-last symbol is a $1$? Such a string must end with either $10$ or $11$. This language can be written as $L = \{ \textrm{all strings of } 0 \textrm{'s and } 1 \textrm{'s ending with } 10 \textrm{ or } 11 \}$.

Since we never know when the next-to-last input occurs, we need to track those two substrings whenever they occur. The following figure shows a DFA for the language $L$.

The state labels reflect the substring just processed that led to each state. Observe how the out-edges from the accepting states behave. The last symbol read before reaching those states becomes the next-to-last symbol on the subsequent move.

DFA accepting strings with a 1 in the third-to-last position

Now let’s consider how to recognize strings over $\{0,1\}$ that end with a $1$ in the third-to-last position. Reading a $1$ starts us on a potential path to acceptance. From there, we’ll read a $0$ or $1$, at which point we’ll have read one of $10$ or $11$. An acceptable string must be of at least length three and end with $100$, $101$, $110$, or $111$. Thus, the language of our interest, is $M = \{ \textrm{all strings of } 0 \textrm{'s and } 1 \textrm{'s ending with } 100,\:101,\:110, \textrm{ or } 111 \}$.

The possibilities that the input ends with $100, 101, 110,$ ...