Regular Languages | Thien Hoang

In this post, we will discuss the concepts surrounding the topic "Regular Languages" like DFA, NFA, regular expressions, and two important theorems, the pumping lemma and Myhill-Nerode theorem.

Finite automaton

A good representation for what is so called finite automaton is a directed graph with a finite number of vertices. Each vertex is called a state. Each edge is assigned with a value called a symbol. The set of all possible symbols is called an alphabet. There is also one node marked as the start state, and some nodes are marked as the accept states. We give this automaton a string s, the following will happen:

current_state = start_state
for character ch in s:
  for edge e in current_state.out_edges:
    if e == ch:
      current_state = e.end_node

You may wonder, what if there are multiple e such that e == ch? Well, this is the formal definition of finite automaton:

Definition: (Deterministic) Finite Automaton. A finite automaton is a tuple , where:

is a finite set of states
is a finite set called the alphabet
is the transition function
is the start state
is the set of accept (final) states

Based on the definition of , you will always find at most one outgoing edge whose symbol concides with the character in the string. Such behavior is called "deterministic", but we will discuss later.

If after browsing through all the characters in s, you end up with a current_state that can be found in , we say the automaton accepts s.

Let's name our automaton (also called "machine") . The set of all strings that accepts is called the language of machine and written . We also say recognizes . is unique to , i.e. one machine recognizes exactly one language. A language is called a regular language if there is some machine that recognizes it.

One common problem is to design an automaton that recognizes a given language. This is very similar to designing an algorithm. The automaton must accept all strings in the language, and reject any string not in the language.

For example, let be the language over which consists of all strings that have "0110" as a substring. Let's design a simple algorithm first.

bool f(string s):
  t = "0110"
  for (int i = 0; i < s.size(); ++i):
    // A
    if (s[i] == '0'): // B
      if (s[i+1] == '1'): // C
        if (s[i+2] == '1'): // D
          if (s[i+3] == '0'): // E
            return true
          else: continue
        else: continue
      else: continue
    else: continue

Notice that I mark some lines as A, B, C, ... They will be the states of our automaton, the states that we care. Before the for-loop, I don't mark any state because it is unnecessary. Now we should find the transition function, i.e. when to change from this state to another state.

The automaton that recognizes the language of all strings that contain 0110 as a substring

Once we reach state , which is the final state, the automaton will continue to process the rest of the string. Since we are guaranteed that the string contains "0110" as a substring, the rest of the string is not important. Hence all outgoing edges of will go back to itself.

Properties of regular languages

If and are regular languages, , , are also regular languages. Hence, , , and (written from low to high priority in term of operator precedence) are called regular operators.

Non-determinism

When two or more outgoing edges of a node have the same label, we call the automaton nondeterministic. Formally,

Definition: Nondeterministic Finite Automaton. An NFA is a tuple , where:

is a finite set of states
is a finite set called the alphabet
is the transition function
is the start state
is the set of accept (final) states

Note: is the null character, also denotes the empty string.

Note: A DFA is automatically an NFA.

Hence when process a string, the following will happen:

current_state = {start_state}
for (character ch in s):
  next_state = {} // empty list
  for (state cs in current_state):
    for (edge e in cs.out_edges):
      if e == ch or e == epsilon:
        next_state.add(e.end_node)
  current_state = next_state

Theorem. Every NFA can be transformed into a DFA.

We can roughly understand why by looking at the algorithm. The current_state is now a subset of , so our DFA should be a tuple , where . The rest of the proof is complicated to present, but should be obvious recognize, so I will stop here.

Regular expression

Regular expression is a way to generalize a language by exploiting its pattern. We use regular operators as operators, and symbols in the alphabet as operands, parentheses are allowed. For example, consider the language over that contains all the strings that have 0110 as a substring, the expression can be written as:

The concatenation operator is sometimes omitted just as the multiplication operator in arithmetic. is just another way of writing which is the short-hand writing of .

Theorem. Any finite automaton can be transformed into a regular expression and vice versa.

Generalized Nondeterministic Finite Automaton

Definition: Generalized Nondeterministic Finite Automaton. A GNFA is a tuple , where

is a finite set of states
is a finite set called the alphabet
is the transition function
is the start state
is the accept (final) state

A GNFA accepts a string where if there exists a list of states such that:

for each , we have

In the graph representation of a GNFA, on each edge, instead of a symbol, there is a regular expression. You move from state to state over an edge if the next few letters in the input string fit the regular expression on that edge.

However, it can be shown that any GNFA that has more than 2 states can be transformed into a GNFA with exactly 2 states. We just need to remove the states sequentially, each time we remove a state, we need to redraw our edges. Suppose that we are removing , we need to bridge all pair of and , where denotes the state that goes into via an edge and denotes the state into which goes via an edge. What regular expression could we assign for our edge ? We need to think: how many ways can we go from to ?

Go directly if there exists an edge between them already.
Go from to , self-loop at for an arbitrary number of times, then go from to .

which implies that:

Note: I used := for simple writing, that means we redefine the mapping between and . You can always define a completely new GNFA so that it will look more formal, more mathematical, and less programming.

Eventually you will end up with a GNFA that contains only and . Based on the source set of , there should be no self loop at any of these two states, i.e. there is only one edge on this graph. The expression on this graph is the regular expression representation of the original GNFA.

Note that a DFA or an NFA is automatically an GNFA, so the algorithm above can also give us the regular expression of the automaton.

Pumping lemma

You may have heard of "Squeeze theorem", định lý kẹp.
Now introducing "Pumping lemma", bổ đề bơm.

Theorem: Pumping lemma. Let A be a regular language. There exists a number such that any string whose length can be divided into three parts satisfying the following conditions:

for any ,

If A is a finite language, it vacuously satisfies the pumping lemma by choosing larger than the size of the longest string in A.

Proof idea

Since is regular, there's a DFA that recognizes it. Let be the number of states in the automaton.

For a string of length at least , it must go through states as the string is emitted. By the pigeonhole principle, it must have reached some state at least twice. The substring that corresponds to the journey from the first appearance to the second appearance of the repeated state is in the lemma. Hence, we can travel in this loop for an arbitrary number of times, or none at all, and can still reach one of the accept state.

Nonregular language

The fact that mathematicians use the phrase "nonregular language" instead of "irregular language" annoys me so much I want to quit my study.

(Please write that quote on my tomb when I die)

The DFA that recognizes the language of all strings containing equal occurences of 01 and 10 as substrings.

Finite automata have limited memory, i.e. finite amount of states, and they cannot recognize language that require infinite states. A famous example is the language . This language is nonregular because it has to remember how many 0's it has read before reading the 1's. There is no upper limit to , hence it requires infinitely many states.

On the other hand, the language of all strings that have an equal number of occurences of 01 and 10 seems like a nonregular because it may have to count the occurences, which can tend to infinity. However it is not necessary to count. Whenever you approach a substring 01 (state C), just wait until you get a 0, then the amounts are balanced. Vice versa, if you approach a substring 10 (state E), just wait until you get a 1. This language is regular.

We usually use the pumping lemma to prove a language to be nonregular by contradiction.

The class of regular languages

I've mentioned that three operators are regular operators, i.e. if A and B are regular languages, then so are . The class of regular languages, however, is also closed under other "operators":

Perfect shuffle of A and B is the language of all strings where and and .
Shuffle of A and B is the language of all strings where and and .
Reverse of a string is obtained by rewriting its character in the opposite order. Reverse of a language is obtained by reversing each string in the language, i.e.
..........

Finite-state Transducer

A finite-state transducer (FST) is an extension of DFA that not only returns "accept" or "reject", but also outputs a string as the input string is processed. Each transition is labelled with two symbols, one specifying the input symbol and the other specifying the output symbol.

current_state = start_state
output_string = "" // empty
for character ch in s:
  for edge e in current_state.out_edges:
    if e.input_symbol == ch:
      current_state = e.end_node
      output_string.add(e.output_symbol)

This means that, it follows the exact process as if it is the DFA, but at each transition it gives us an output symbol. The output symbol does NOT affect the traversal. Think of it as a debugger and you are writing to the screen the value of some variable.

Myhill-Nerode Theorem

Let be two strings in the language .

We say that and are distinguishable by if some string (can be empty) exists and one of the strings and is in , but not both. In this case, is called the distinguish extension.
We say that they are indistinguishable by if for any string we have "". If and are indistinguishable by , we write .

Note: x and y are not necessarily in L. They are in fact any strings made from the alphabet on which L is based, i.e. .

Theorem. is an equivalence relation.

which implies that divides into equivalence classes. We call them the equivalence classes of . The index of is the number of equivalence classes. The index can be infinite or finite.

Properties:

If then . It is true because if xz and yz are distinguishable, say w is the distinguish extension, hence either xzw or yzw belongs to L but not both. zw is the distinguish extension for x and y, which contradicts to the assumption .
If and then . It is true because if , x and y are distinguishable when choose the empty string as the distinguish extension, which contradicts to the assumption .

Theorem: Myhill-Nerode Theorem. is regular iff it has finite index, and its index is the number of states in the DFA recognizing it.

Proof

1. Prove that if L is recognized by some DFA with n states, then its index is at most n.

We partition into n sets, set contains all the strings that when given to A will cause A to stop at state i. It can be seen that, if x and y are in the same set , for any string z, xz and yz will cause A to stop at the same state, and therefore both of them are either rejected or accepted, i.e. (though, it is possible for some strings x and y of different sets to be equivalent by L). In conclusion, is a subset of an equivalence class.

Consider the map from the set of n sets , to the set of equivalence classes of . Any string x belongs to some set and belongs to some equivalence class of , this means any equivalence class has a pre-image, i.e. the map is surjective. The number of equivalence classes does not exceed n, the number of states.

2. Prove that if the index of is a finite number n, it is recognized by a DFA with n states.

We have divided into n equivalence classes. It is possible to construct a DFA such that if string x is from the class i, the automaton shall stop at state i, in that case we say the string x corresponds (just a made-up word) to state i. The construction of transitions can be shown recursively:

State i is the start state if class i has the empty string. Note that there is only one such state.
The transition from some state i to state j on the input symbol y if for an arbitrary string x corresponding to state i, xy corresponds to state j. It doesn't matter which x is chosen, because we've shown that if then , so the next state will always be the same regardless of x.
State i is an accept state if class i contains a string that belongs to L. In fact, we've shown in the properties section that if it contains a string in L, then all other strings in this class are also in L.

We can continue by proving this DFA recognizes L, but I would just stop here.

3. Conclusion

Combining the two results above gives us the Myhill-Nerode theorem.

Reference source

Wikipedia - Myhill-Nerode Theorem
Michael Sipser - "Introduction to the Theory of Computation" (3rd ed.)
Wikipedia - Pumping Lemma for Regular Languages