2.2.2 Formal Languages

We can use the same graph in Fig. 2.10 as an automaton for GENERATING sheeptalk. If we do, we would say that the automaton starts at state $ q_0 $, and crosses arcs to new states, printing out the symbols that label each arc it follows. When the automaton gets to the final state it stops. Notice that at state 3, the automaton has to chose between printing out a ! and going to state 4, or printing out an a and returning to state 3. Let's say for now that we don't care how the machine makes this decision; maybe it flips a coin. For now, we don't care which exact string of sheeptalk we generate, as long as it's a string captured by the regular expression for sheeptalk above.

Formal Language: A model which can both generate and recognize all and only the strings of a formal language acts as a definition of the formal language.

A formal language is a set of strings, each string composed of symbols from a finite symbol-set called an \textit{alphabet} (the same alphabet used above for defining an automaton!). The alphabet for the sheep language is the set $ \Sigma = \{a, b, !\} $. Given a model $ m $ (such as a particular FSA), we can use $ L(m) $ to mean “the formal language characterized by $ m $”. So the formal language defined by our sheeptalk automaton $ m $ in Fig. 2.10 (and Fig. 2.12) is the infinite set:

$$ L(m)=\{baa!,baaa!,baaaa!,baaaaaa!,baaaaaa!,\ldots\} $$

The usefulness of an automaton for defining a language is that it can express an infinite set (such as this one above) in a closed form. Formal languages are not the same as natural languages, which are the kind of languages that real people speak. In fact, a formal language may bear no resemblance at all to a real language (e.g., a formal language can be used to model the different states of a soda machine). But we often use a formal language to model part of a natural language, such as parts of the phonology, morphology, or syntax. The term generative grammar is sometimes used in linguistics to mean a grammar of a formal language; the origin of the term is this use of an automaton to define a language by generating all possible strings.