asg2

Shai Simonson     CSC 384     Theory of Computation

Assignment 2  (40 points)

Due:  Wednesday, October 23

1.  Minimizing FSM's  (10 points) 

Consider the Finite Automaton above.

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)

1. You must prove that your choice is correct. If regular, exhibit a machine, expression, or grammar;  if not regular, 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)

1. 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. Has at least one string w that has 111 as a substring.

   2. Is co-finite. (a set is co-finite if and only if its complement is finite).

   3. Contains all strings of the form 0*1*

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. 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.

 Write a program to implement Hopcroft's FSM minimization algorithm that runs in O(n log n) time, in contrast to the O(n2) algorithm we described in class, known as Moore's algorithm.  Here is a nice place to look at some examples.