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 aa and ending with bb

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

Get hands-on with 1200+ tech skills courses.