SKEDSOFT

Regular Expressions to NFA

1. For any x in S, the regular expression denotes the language {x}. The NFA (with a single start state and a single final state) as shown below, represents exactly that language.

1. The regular expression l denotes the language {l}that is the language containing only the empty string.

1.  The regular expression Æ denotes the language Æ;  no strings belong to this language, not even the empty string.

1. For juxtaposition, strings in L(r1 ) followed by strings in L(r2 ), wechain the NFAs together as shown.
    

1. The “ ” denotes “or” in a regular expression, we would use an NFA with a choice of paths

1. The star (*) denotes zero or more applications of the regular expression, hence a loop has to be set up in the NFA.