Chapter 4 - Regular Expressions

Question 1

What does L(theta) mean/translate into?

Answer 1

Theta i.e. the empty set

Question 2

What does L(epsilon) mean/translate into?

Answer 2

The set of the empty word

Question 3

What does L(X) mean/translate into?

Answer 3

L(X) = {x}, where x is an element of the associated alphabet

Question 4

What does L(E + F) mean/translate into?

Answer 4

L(E + F) = L(E) Union L(F)

Question 5

What does L(EF) mean/translate into?

Answer 5

L(EF) = L(E)L(F)

Question 6

What does L(E*) mean/translate into?

Answer 6

L(E) = L(E)

Question 7

What does L((E)) mean/translate into?

Answer 7

L((E)) = L(E)

Question 8

How would you go about generating an NFA from a regular expression involving the generation of multiple NFAs?

Answer 8

1. Generate each separate NFA based on the structure of the regular expression e.g. if it is N(ab), then generate the NFAs for a* and b*.
2. Combine the two together by splitting a connection connected to a final state, and link it to the other final state for the empty word in the 2nd NFA, as well as its initial state.
3. Remove dead ends that lead to nowhere useful