Answer only please. No explanation required answer what you can.

1. If L and M are regular expressions, which of the following is not a regular expression?

A. L + M

B. L M

C. L*

D. (LM)*

2. What is the right language that describes regular expression ab* + c?

A. {a, c, b, bb, bbb, , bn, }

B. {?, a, c, b, bb, bbb, , bP

n

P, }

C. {?, a, c, ab, abb, abbb, , abP

n

P, }

D. {a, c, ab, abb, abbb, , abPnP, }

3. What is the right regular expression that describes the following language?

{?, ab, abbb, abbbbb, , abP

2n+1

P, }

A. ab*

B. ?+ab*

C. a(bb)*b

D. ?+ a(bb)*b

4. What is the right regular expression that describes the following language?

{?, a, b, c, aa, bb, cc, , aPnP, bPnP, cPnP, }

A. a + b + c

B. ? + a + b + c

C. a* + b* + c*

D. a*b*c*

5. What is the right regular expression for strings whose length is multiple of 3 over the alphabet {a, b}?

A. (a + b)*

2

B. (aaa + bbb)*

C. (aaa)* + (bbb)*

D. ((a + b + c)( a + b + c)(a + b + c))*

6. What is the correct simplified form of the following regular expression?

aa(b* + a) + a(ab* + aa)

A. b* + a

B. a(b* + a)

C. aa(b* + a)

D. aa(b* + a) + aa(b* + a)

7. Find the correct equality:

A. ?* = ?

B. ?* = ?

C. ?* = ?

D. ?* = ??

8. Find the incorrect equality:

A. R* = (R*)*

B. R* = R + R*

C. R* = RR*

D. R* = ? + R*

9. Which of the following is untrue about DFA?

A. Each state emits one labeled edge for each letter of alphabet A.

B. One state is designated as the start state.

C. There must be at least a final state

D. There may not be any final states

10. With the following DFA, which state is a final state?

A. 0

B. 1

C. 2

D. It doesnt have final state

11. Referring to the DFA in Question 10, what is the correct transition function for state 1?

A. T(1, a) = 1; T(1, b) = 1

B. T(1, a) = 1; T(1, b) = 2

3

C. T(1, a) = 2; T(1, b) = 1

D. T(1, a) = 2; T(1, b) = 2

12. Which input string is accepted by the DFA in Question 10?

A. ?

B. b

C. ba

D. baa

13. Referring to the DFA in Question 10, what does T(0, bba) equal to?

A. 0

B. 1

C. 2

D. Undefined

14. The following is a DFA designed for regular expression ba*. Find proper labels in numbered positions for the transitions.

A. 1 a; 2 b; 3 a; 4- b; 5 a, b

B. 1 b; 2 a; 3 a; 4- b; 5 a, b

C. 1 a; 2 a; 3 b; 4- b; 5 a, b

D. 1 b; 2 b; 3 a; 4- a; 5 a, b

15. What is untrue about NFA?

A. ?-edges are allowed

B. There is no requirement to emit edges from a state

C. Multiple edges with the same letter can be emitted from a state

D. It is a special case of DFA

16. Given the following NFA, what is the correct transition function for state 0?

A. T(0, a) = 0; T(0, b) = 1

B. T(0, a) = {0}; T(0, b) = {1}; T(0, ?) = ?

C. T(0, a) = {0, 1}; T(0, b) = ?; T(0, ?) = ?

D. T(0, a) = ?; T(0, b) = {0, 1}; T(0, ?) = ?

17. Which of the following input strings is accepted by the NFA in Question 16?

1

2

3

4

5

4

A. ?

B. a

C. b

D. ab

18. The following figure shows the first 2 steps of transforming an NFA to regular expression. What is the correct label for the transition with a question mark?

A. ba*a

B. ab*b

C. bb*a

D. aa*b

19. Transform the following single state NFA into a regular expression, where state 0 is the start state and final state. What is the resultant regular expression?

T(0, a) = {0}, T(0, b) = {0}

A. a* + b*

B. (a + b)*

C. a*b*

D. (ab)*