3.1.1 FSAs, Regular Expressions, and Regular Languages

Different views on the same matter.

First, let's go back to finite state automata. We said in Chapter 1 that the languages that FSAs can recognize are called regular languages. But there is another way of defining regular languages: Regular languages are exactly those languages that can be represented by regular expressions. And from this it follows that every automaton corresponds to a regular expression and vice versa. So, we get the following picture: