The most restricted class of language we will consider is the regular languages. The following statements are equivalent:

  • L is a regular language.
  • There exists a deterministic finite automaton (DFA) that accepts A.
  • There exists a nondeterministic finite automaton (NFA) that accepts A.
  • There exists a regular grammar that generates A.
  • There exists a regular expression for A.

In other words, given any one of {DFA, NFA, regular expression, regular grammar}, you can generate all of the others. Proving that a language is regular is done simply by providing one of these objects that accepts it.

What regular languages have in common is that they can be recognized by a machine with a finite number of states and no memory. For example, consider the language whose words are all strings consisting of an even number of a’s. We can prove that this is a regular language by giving a regular expression for it: L=(aa)*. Alternatively, consider the diagram below.

The arrow coming from the upper left indicates that the circle it points to is the start state; the second circle inside it indicates that this is also an accept state. When the start state is also an accept state, the machine accepts λ. The loop indicates that the machine can read in the string ‘aa’ and return to the start state. This is actually shorthand; the full DFA looks like this:

Notice that when the machine reads in an a from the input, it moves into the second state, which is not an accept state. If there is no more input, it will reject the string; when it sees another a, it moves back to the accept state.

The way a deterministic finite automaton works is that it reads the entire  input. At every state, there is exactly one transition (the arrows) from that state to another state for every possible input; that is, every character in the alphabet. If the machine is in an accept state when the input is empty, then the string belongs to the language and the machine accepts it; otherwise, it rejects the string.

A nondeterministic finite automaton is  very similar; in fact, every DFA is also a NFA. A NFA simply has fewer restrictions, as follows. First off, there can be more than one transition, or no transitions, going out of a state for a given letter of the alphabet. If a letter is read from the input and there is no corresponding transition that can be taken, the machine rejects the string. If there are several legal transitions, the machine follows all of them. Another way of looking at it is to say that the machine “guesses” which transition will eventually lead to an accept state when the entire string has been read in, and always chooses the correct one; unlike in a deterministic machine, we don’t always know which path will be followed. The other difference is that NFAs can have λ transitions, which means that you can move from one state to another without reading in any input.

Important: a common mistake is to think that a λ transition means to read any character from the input; this is NOT the case! When you follow a line marked with a λ, that means to go to the next state without reading anything from the input.

Any language that has an NFA also has a DFA; in a later section, we will cover an algorithm for creating the DFA given a corresponding NFA. Of course, changing a DFA into an NFA is easy: just do nothing!


Leave a Reply