The Theory of Formal Languages
In this episode, Kyle and Linhda discuss the theory of formal languages. Any language can (theoretically) be a formal language. The requirement is that the language can be rigorously described as a set of strings which are considered part of the language. Those strings are any combination of alphabet characters in the given language.
These concepts are relevant to artificial intelligence in that we’d like to consider what sort of machine is required to be able to recognize each language. Recognizing a language involves being able to determine whether or not a given string is a part of that language.
For example, if we consider a subset of the English language that is only lower case, then we could enumerate all the strings, which might look something like this:
aaaaaaaaaaaa
aaaaaaaaaaab
aaaaaaaaaaac
...
data skeptic
data skeptid
...
zzzzzzzzzzzz
We discuss “sheep” language, which takes the form (described here as a regular expression): ba+, meaning that all valid utterances start with b and must be followed by at least one a. This trivial language requires only a trivial finite state machine with four states. Kyle says 2 states in the episode, but it’s really 4.
. Although limited, they are often extremely powerful tools. Further, their simplicity makes it possible to state formal proofs about their results, and demonstrate mathematically that they correctly do the job they are supposed to do in a bug free way. That’s something which is difficult if not impossible to do for a typical software application.</p>
<p>Any language that can be recognized by a FSA is called a regular language.</p>
<p>There exist a series of proofs known as “pumping lemmas”, the most famous of which states that there are languages which are not regular. The canonical language is one which has some number of <code>b</code>s followed by precisely the same number of <code>a</code>s (i.e. <code>b*a*</code>). Since this requires one to “remember” the number of <code>b</code>s, no FSA can do it. Sure, you can construct an FSA that can recognize a subset of this language up to a certain length, but recognizing it completely would require an infinite number of states, and that’s not allowed right there in the name.</p>
<p>The simplest machine capable of recognizing <code>a*b*</code> is a push down automata (PDA). A PDA has a <a href=)
stack for a memory. Clearly, that’s limiting, but it’s just enough to meet our needs for this other language.
I hope that it’s quite obvious such a machine is hopeless for recognizing English sentences. This is sometimes a point of confusion, because a PDA is totally capable of recognizing the general grammar of an English sentence. The process of diagraming a sentence into noun phrases, verb phrases, and further nestings down to the individual parts of speech can be accomplished by a PDA. But recognizing a true English sentence from a gibberish sentence that fits the general form is not possible with a PDA. For that, you need a Turing machine which is capable of computing anything which is intuitively computable.
There are other levels in the hierarchy of formal languages, but FSA < PDA < TM covers the (arguably) most important there.
