Shai Simonson         CS 301         Languages and Automata

Assignment 2  (40 points)

Due:  Friday, February 28


1.  Minimizing FSM's  (10 points)
 

    Consider the Finite Automaton below.

    a.  Construct the smallest Deterministic Finite Automaton which accepts the same language.  Don't forget to include a dead state if there is nowhere to go in the non-deterministic machine from some state on some symbol. 

    b.  Draw a regular expression that represents the language accepted by your machine.

    c.  Write down a Regular (Linear) Grammar that generates it.

2.  Regular or Not?  (18 points)

    You must prove that your choice is correct. Use the pumping lemma, and/or closure arguments.
     

    1. The set of strings that have an even number of double zeros in them. (Note that three zeros in a row count as 2 double zeros).
    2. The set of strings over the alphabet {0} of the form 0n where n is not a prime.
    3. The set of all strings of the form xwxR where x and w are non-empty strings over the alphabet {0,1}, and the big R over the x means the reverse of x.
    4. The set of all strings over the alphabet {0} whose length is n! for some n > 0.
    5. The set of all binary strings that read backwards the same as forwards (palindromes).
    6. {www | w is a binary string}
    7. {0m1n | m is not equal to n}
    8. {0m1n0m | m,n >= 0}
    9. {0i1j0k | i,j,k >= 0,if i=1 then j=k}
3. Decision Algorithms  (6 points)

    Recall that a decision algorithm is an algorithm that returns a yes or no answer.   Give decision algorithms to determine if a Regular set

    1. Contains all strings of the form 0*1*.
    2. Is co-finite. (a set is co-finite if and only if its complement is finite).
    3. Has at least one string w that has 111 as a substring.
4. Regular Grammars (4 points)
Recall that a right-linear grammar is one where every production is either in the from A->aB or A ->b, where a and b are terminal symbols. and A and B are non-terminal symbols. Every regular set can be generated by a right-linear grammar and every right-linear grammar generates a regular set.  Thus, a right-linear grammar is equivalent to a finite state machine, and we call a right-linear grammar regular..

a.  Write down a right-linear grammar to generate the set of strings that are evenly divisible by 5 when interpreted as a binary string.
b.  A left-linear grammar is a context-free grammar where each production must be either in the form A->Ba, or A->b, where a and b are terminal symbols and A and B are non-terminals.  Left-linear grammars are also equivalent to finite state machines. Explain how to convert a given finite state machine, to an equivalent left-linear grammar. You may use an example to illustrate.
Hint:  Let L be the language generated by some right-linear grammar G.  Reversing the right sides of each production in G creates a left linear grammar that generates the reverse of L.

5.   Single Symbol Regular Languages (2 points)
    1. Prove that every language of the form 0mx+b, where m and b are non-negative integer constants and x ranges from 0 to infinite, is regular.
    2. Describe a regular set over the alphabet {0} that is NOT of the form from part (a).
    3. Extra Credit: Characterize all regular sets over the alphabet {0}, and prove your answer. That is, prove that every regular set over the alphabet {0} is of some particular form.


Extra Credit - Minimizing FSM’s.   (Warning:  Very Challenging).

     Describe a method to implement the FSM minimization algorithm that runs in O(n log n) time, rather than O(n2). Write a program implementing your method.