CS 254: Automata and Computability

Assignment #1

Due on paper by 8:30AM Wednesday, April 7.

  1. For this problem, let Σ = {a, b}.

    1. Draw a DFA M1 for which L(M1) = {x ∈ Σ* | x begins with a}.
    2. Draw a DFA M2 for which L(M2) = {x ∈ Σ* | #a(x) is even}.
    3. Use the Product Construction described on page 22 of Kozen to build a DFA M3 for which L(M3) = L(M1) ∩ L(M2).
    4. Is it possible to construct a DFA for L(M3) using fewer states than M3 has? If so, show such a DFA. If not, give a brief explanation (not a formal proof) why not.

  2. Consider the DFA M described by:

    Q = {0, 1} Σ = {a, b} s = 0 F = {1} and
    δab
    001
    111
    1. Describe L(M) in English.
    2. Prove your answer correct.

  3. In which the intrepid students investigate the regularity of finite sets...

    1. If I give you a finite set of strings over an alphabet Σ, is it possible to create a DFA M for which L(M) is equal to that finite set? (Hint: yes.) Briefly describe a procedure for doing so.
    2. Illustrate your procedure by drawing a DFA named M over the alphabet {a, b} for which L(M) = {aba, abb, abba, baa, baba}. (This set, by the way, is the complete set of English words of three or more letters consisting entirely of a's and b's, according to SOWPODS.)

  4. For each of the following, provide Python code using the re module to accomplish the specified task. (Once you have something that seems to be working, think again about ways in which a string could fool your regular expression.)

    1. Extract the first word in the string s that both begins and ends with a lower-case letter.
    2. Print the starting and ending indices of all the words in the string s that both begin and end with a lower-case letter. For example, if s = "The moose is disgruntled.", you should print something like:
      4 9 10 12 13 24
      Note that the ending index is the index of the character immediately following the word.
    3. Replace all occurrences in the string s of the words "Doctor" or "Dr." into "The Good Doctor" or "The Good Dr.", respectively, except when "Doctor" or "Dr." is followed by " Evil". That is, "I enjoy conversations with Dr. Schweitzer" would become "I enjoy conversations with The Good Dr. Schweitzer", but "Doctor Evil is not very nice" would remain unchanged.
    4. Try to transform the string s into Ubbi dubbi. Once you have a rough version of an Ubbi dubbi translator, describe the errors your version will make. Are regular expressions capable of fixing those errors?