COT 6315/CS 710-R Spring 1998 -- Midterm Examination 1

Midterm Examination 1

This open-book examination is to take 50 minutes. Please answer four of the six questions presented below. Make sure you answer briefly but clearly. Extraneous incorrect information will cause the score for otherwise correct answers to be lowered.

No aid other than your textbook is allowed on this examination.

Pledge (Must be signed according to UF Honor Code)

On my honor, I have neither given nor received unauthorized aid in doing this assignment.
________________________________ (signature)

Examination Questions

Use a machine construction argument like that of Theorem 1.12 in Sipser to show that if L1 and L2 are disjoint languages (that is, if their intersection is empty), and if both L1 and the union of L1 and L2 are regular, then L2 is regular as well.
```
       



























       
       
```
Is the following language over the set {0,1} regular or non-regular?
{ w | whas an equal number of occurrences of substring 001 and 110}
Demonstrate the correctness of your answer by providing either a machine accepting the language or a pumping lemma contradiction.
```
       





























       









       
```
Demonstrate that just because a language L is regular, that does not imply that any subset of L is regular. In other words, give an example of a non-regular language that has a regular superset.
```
       










       
```
Demonstrate that if language L is accepted by a DFA, then there is a DFA accepting L^R as well. Do not use regular expressions in your argument.
```
       










       
```
Use the definition of a regular expression to give an algorithm which, given a regular expression E describing language L will produce a regular expression describing L^R. Do not use an machine constructions in your argument.
```
       








       
```
Convert the machine described by the following diagram into a regular expression. Either apply an algorithm known to be correct, or convincingly argue the correctness of your result.
```
       









       
```