COT 6315/CM 710-R Formal Languages and Computation Theory (Summer 2000)

Examination 1

NOTE: Complete exactly 5 of the following 6 questions. Clearly note which question you do NOT want graded.

1. Show that if L is the language over alphabet {0,1} defined by L = {x | x is the binary representation of a number and x mod 3 = 0}, then L is a regular language.

2. Prove or disprove the following claim: the language abⁿacⁿ is regular.

3. Consider the DFA M = ({q₀,q₁,q₂}, {0,1}, d, q₀, {q₀}) with transition function d defined as:

   	0	1
   q0	q0	q1
   q1	q1	q2
   q2	q2	q0

   Draw a state transition diagram for M then construct a regular expression for M using the CONVERT procedure described in Sipser's text. Show each intermediate GNFA generated by your application of the procedure.

4. Consider the alphabet containing four distinct symbols S = {[0/0], [0/1], [1/0], [1/1]}.

   A string of symbols in S gives two sequences of binary digits and represents two distinct binary numbers: the one whose bits are to the left of each slash and the one whose bits are to the right of each slash. Thus the string [1/0][1/1][0/1] is interpreted as the two numbers 110 and 011, representing 6 and 3 in the left and right positions respectively.

   Design a determinitstic finite automaton to accept those strings over S in which the left number is exactly twice the right number.

5. Prove that any finite language is regular.

6. Demonstrate that the regular languages are closed under intersection by showing how one can combine two DFAs M₁ and M₂ into a new DFA M₃ whose language is the intersection of the languages of M₁ and M₂.