COMS W3261 CS Theory
Lecture 6: Properties of Regular Languages - II

1. Decision Problems for Regular Languages

• We can ask whether a representation of a language has a given property. Such a question is often called a decision problem.
• If there is an algorithm to answer the question, we say the problem is decidable. For decidable problems we are interested in how quickly a question can be answered as a function of the size of the representation of the language.
• The emptiness problem is to decide whether the language denoted by a given representation is empty.
• Given a finite automaton for a regular language, we can answer the emptiness problem by determining whether there is a path from the start state to a final state. This can be answered in O(n²) time where n is the number of states in the automaton.
• The membership problem is to decide whether a particular string is in the language denoted by a given representation.
• Given a DFA D for a regular language and an input string w, we can answer the membership problem by simulating D processing w beginning in the start state. This can be answered in O(|w|) time.

2. Testing Equivalence of States

• Given a DFA D for a regular language, we say two distinct states p and q are equivalent if, for all input strings w, δ*(p, w) is a final state iff δ*(q, w) is a final state.
• This says the two states δ*(p, w) and δ*(q, w) are either both accepting or both nonaccepting.
• If two states of a DFA are not equivalent, then we say they are distinguishable.
• Here is what is known as the table-filling algorithm for computing all pairs of distinguishable states of a DFA:
• Input: a DFA D = (Q, Σ, δ, q₀, F).
• Output: a table T of all pairs of distinguishable states.
• Method:

for all states p and q do
   if p is final and q is nonfinal
      add {p, q} to T
for all states p and q do
   for all input symbols a do
      if δ(p,a) and δ(q,a) are in T then
         add {p, q} to T
until no more pairs can be added to T

• Theorem: If two states p and q are not distinguishable by the table-filling algorithm, then p and q are equivalent.

3. Testing Equivalence of DFA's

• We can use the table-filling algorithm to test the equivalence of two DFA's by testing the equivalence of their start states.
• The DFA's are equivalent iff their start states are equivalent.

4. Minimizing the Number of States in a DFA

• We can use the table-filling algorithm as a subroutine to minimize the number of states in a DFA.
• The minimization algorithm:
• Input: a DFA A = (Q_A, Σ, δ_A, q_A, F_A).
• Output: an equivalent minimum-state DFA B = (Q_B, Σ, δ_B, q_B, F_B).
• Method:

1. Eliminate any state that cannot be reached from the start state.
2. Compute the sets of all equivalent states using the table-filling algorithm.
3. Partition the states into blocks so that
      all states in the same block are equivalent and
      no pair of states from different blocks are equivalent.
4. Construct the minimum-state DFA B as follows:
   a. QB is the set of blocks of equivalent states.
   b. If R and S are blocks containing the states p and q of A, respectively,
         then δB(R, a) = S if δA(p, a) = q.
   c. qB is the block containing qA.
   d. A state S is in FB if S contains a state in FA.

• Theorem: L(B) = L(A) and no DFA equivalent to A has fewer states than B.
• This theorem captures an important property about regular languages. Every regular language is defined by a minimum-state DFA that is unique up to renaming of states.

5. Practice Problems

1. Let L be a regular language over the alphabet Σ. Show that it is decidable whether L = Σ*.
2. Prove that the two regular expressions (a+b)* and (a*b*)* generate the same language by showing that their minimum-state DFA's are the same (up to renaming of states).
3. Describe an algorithm to determine whether two regular expressions are equivalent. What is the running time of your algorithm?
4. Minimize the number of states in the following DFA having the start state A, the set of final states {C, E, F, G }, and the following transition function:
   
   

   State	Input Symbol
   	0	1
   A	B	D
   B	B	C
   C	D	E
   D	D	E
   E	B	C
   F	C	G
   G	F	E

   
   
5. Consider the function on languages noprefix(L) = { w in L | no proper prefix of w is a member of L}. Show that the regular languages are closed under the noprefix function.
6. [Hard but a fundamental characterization of regular languages] An equivalence relation R on a language L contained in Σ* is right invariant if xRy implies xzRyz for all z in Σ*. R is of finite index if it partitions L into a finite number of equivalence classes. Show that L is regular if and only if it is the union of some of the equivalence classes of a right-invariant equivalence relation on L of finite index.

6. Reading

• HMU: Ch. 4