The question of the equality of two languages is also an important practical
issue. Often several definitions of a programming language exist, and we need to
know whether, in spite of their different appearances, they specify the same
language. This is generally a difficult problem; even for regular languages the
argument is not obvious. It is not possible to argue on a sentence-by-sentence
comparison, since this works only for finite languages. Nor is it easy to see the
answer by looking at the regular expressions, grammars, or dfa's. An elegant
solution uses the already established closure properties.
Theorem 4.7
Given standard representations of two regular languages L 1 and L 2 , there exists
an algorithm to determine whether or not L 1 = L 2 .
Proof: Using L 1 and L 2 we define the language
By closure, L 3 is regular, and we can find a dfa M that accepts L 3 . Once we have
M we can then use the algorithm in Theorem 4.6 to determine if L 3 is empty. But
from Exercise 8, Section 1.1, we see that L 3 = ∅ if and only if L 1 = L 2 .
These results are fundamental, in spite of being obvious and unsurprising.
For regular languages, the questions raised by Theorems 4.5 to 4.7 can be
answered easily, but this is not always the case when we deal with other
language families. We will encounter questions like these on several occasions
later on. Anticipating a little, we will see that the answers become increasingly
more difficult, and eventually impossible to find.
EXERCISES
For all the exercises in this section, assume that regular languages are given in
standard representation.
1. Show that there exists an algorithm to determine whether or not w ∈ L 1 − L 2 ,
for any given w and any regular languages L 1 and L 2 .
issue. Often several definitions of a programming language exist, and we need to
know whether, in spite of their different appearances, they specify the same
language. This is generally a difficult problem; even for regular languages the
argument is not obvious. It is not possible to argue on a sentence-by-sentence
comparison, since this works only for finite languages. Nor is it easy to see the
answer by looking at the regular expressions, grammars, or dfa's. An elegant
solution uses the already established closure properties.
Theorem 4.7
Given standard representations of two regular languages L 1 and L 2 , there exists
an algorithm to determine whether or not L 1 = L 2 .
Proof: Using L 1 and L 2 we define the language
By closure, L 3 is regular, and we can find a dfa M that accepts L 3 . Once we have
M we can then use the algorithm in Theorem 4.6 to determine if L 3 is empty. But
from Exercise 8, Section 1.1, we see that L 3 = ∅ if and only if L 1 = L 2 .
These results are fundamental, in spite of being obvious and unsurprising.
For regular languages, the questions raised by Theorems 4.5 to 4.7 can be
answered easily, but this is not always the case when we deal with other
language families. We will encounter questions like these on several occasions
later on. Anticipating a little, we will see that the answers become increasingly
more difficult, and eventually impossible to find.
EXERCISES
For all the exercises in this section, assume that regular languages are given in
standard representation.
1. Show that there exists an algorithm to determine whether or not w ∈ L 1 − L 2 ,
for any given w and any regular languages L 1 and L 2 .