1 Which language is described by regular expression ab c A

1. Which language is described by regular expression ab* + c?

A.

{, a, c, ab, abb, abbb, …, abn, …}

B.

{, a, c, b, bb, bbb, …, bn, …}

C.

{a, c, ab, abb, abbb, …, abn, …}

D.

{a, c, b, bb, bbb, …, bn, …}

2. Which NFA is the resultant NFA transformed from the following grammar?

S aS | T

T bbT |

3. What is untrue about NFA?

A.

-edges are allowed

B.

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

C.

There is no requirement to emit edges from a state

D.

It is a special case of DFA

5. 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 in S, s ~ t if for all strings w in A*,

A.

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

B.

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

C.

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

D.

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

Solution

1. C. {a, c, ab, abb, abbb, …, abn, …}

2. S aS | T

3. D. It is a special case of DFA.

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