Theory of computation

1. What is the language of this expression? (a U b)* (b U ba U baa) U l U a U aa considering the alphabet is S = {a, b}.

2. Do the following strings belong to this language? c*(b U ac*)* acabacc bbaaacc Explain your answer clearly and briefly.

3. Grammar, automaton, and regular expressions can be considered as a tool in the field of regular language. What is their role (functionality)? In other words, what does each one do for language?

4. In your own words and briefly, define expression graph.

5. When an NFA is converted to its equivalent DFA, in your own words, answer the following questions:

a. In the newly produced DFA there may be some useless states. What is a useless state and what should be done about it?

b. Which states would be start and final states?

c. How many states would the new DFA have?

6. Explain in simple English, what is the difference between these languages. In other words, what are the sets of strings of these expressions? (a U b)*b(a U b)*b (a U b)* and a*ba*ba*

7. Is regular expression definition of a language unique? If no, give an example.

8. Give the regular expression for the set of strings over {0, 1} that do not end in 111.