Answer only. 20. The following figure shows the first 3 steps of transforming regular expression a(a* + b)* to an NFA. What is the label of the transition with a question mark in Step 3?

Start-->O----a(a* + b)*----->(O)

Start-->O----a---->O-----(a* + b)*----->(O)

Start-->O----a---->O----?---->O---?--->(O)

A. a* + b

B. (a* + b)*

C. a

D. a, b

21. Given the following NFA, what is the ?-closure of state 0?

a b ?

Start 0 ? {1, 2} {1}

1 {2} {0} ?

Final 2 ? {2} {1}

A. {0}

B. {1}

C. {0, 1}

D. {0, 1, 2}

22. Referring to the NFA in Question 21, what is ?({0, 1})?

A. {0}

B. {1}

C. {0, 1}

D. {0, 1, 2}

23. The following is the DFA table constructed from the NFA in Question 21. What is the missing entry?

a b

S {0, 1} {2} ?

F {0, 1, 2} {2} {0, 1, 2}

F {2} ? {2}

A. ?

B. {0, 1}

C. {2}

D. {0, 1, 2}

24. Given the following DFA, what is set E0 for transforming the DFA to minimum state DFA?

a b

Start 0 1 2

1 3 1

2 3 2

Final 3 3 3

A. {{0, 1}, {2, 3}}

B. {{0, 1}, {0, 2}, {1, 2}}

C. {{0, 3}, {1, 2}}

D. {{0, 1}, {0, 2}, {0, 3}, {1, 2}, {1, 3}, {2, 3}}

6

25. Given the following DFA, set E0 is constructed to transform the DFA to minimum state DFA. What is E1?

a b

Start 0 1 2

1 3 1

2 3 2

Final 3 3 3

E0 = {{0, 1}, {0, 2}, {1, 2}}

A. E1 = {{1, 2}}

B. E1 = {{0, 1}, {1, 2}}

C. E1 = {{0, 2}, {1, 2}}

D. E1 = {{0, 1}, {0, 2}, {1, 2}}

26. Let S be the set of states that can be reached from the start state of a DFA over A. The definition of the equivalence relation of states is: For states s, t ? S, s ~ t if for all strings w ? A*,

A. T(s, w) and T(t, w) are identical.

B. T(s, w) and T(t, w) are both final.

C. T(s, w) and T(t, w) are both nonfinal.

D. either T(s, w) and T(t, w) are both final or both nonfinal.

27. Given the following DFA, are state 0 and 1 equivalent?

A. True

B. False

28. The following procedure shows the computation of set Eis for a DFA. What states are equivalent based on the computation?

A. 1 ~ 5 only

B. 2 ~ 4 only

C. 1 ~ 5 and 2 ~ 4

D. 1 ~ 2 ~ 4 ~ 5

29. Given the following DFA, find out what states are equivalent.

7

A. 1 ~ 2

B. 2 ~ 3

C. 1 ~ 3

D. 1 ~ 2 ~ 3

30. Given the following DFA and the fact that 1 ~ 5 and 2 ~ 4, what is the transition function for state [1] in the corresponding minimum state DFA?

A. T([1], a) = 5, T([1], b) = 2, T([1], c) = 1

B. T([1], a) = 5, T([1], b) = 4, T([1], c) = 5

C. T([1], a) = [1], T([1], b) = [2], T([1], c) = [1]

D. T([1], a) = [1], T([1], b) = [2], T([1], c) = [3]

31. Which of the following grammars is a regular grammar?

A. S -> aS | b

B. S -> aSa | b

C. S -> SaS | b

D. S -> aS | Sa | b

32. Which of the following grammars is not a regular grammar?

A. S -> aS | b

B. S -> Sa | b

C. S -> aaS | b

D. S -> aS | Sa | b

33. Which of the following grammars is a right regular grammar?

A. S -> abS | ab

B. S -> aSS | b

C. S -> SaS | b

D. S -> aSa | b

34. Which of the following grammars is a left regular grammar?

A. S -> abS | ab

B. S -> aSb | ba

C. S -> Sab | ab

D. S -> SSa | b

35. Which of the following is a left regular grammar for the language represented by regular expression (a +b*)a?

A. S -> Ta; T -> a | bT

B. S -> Ta; T -> a | U; U -> bU | ?

C. S -> Ta; T -> a | U; U -> Ub | ?

D. S -> aT; T -> a | U; U -> Ub | ?