Building Regular Expressions
1 min read
Regular Expressions to NFA
- 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.
- The regular expression l denotes the language {l}that is the language containing only the empty string.
- The regular expression Æ denotes the language Æ; no strings belong to this language, not even the empty string.
-
For juxtaposition, strings in L(r1 ) followed by strings in L(r2 ), wechain the NFAs together as shown.
- The “ ” denotes “or” in a regular expression, we would use an NFA with a choice of paths
- The star (*) denotes zero or more applications of the regular expression, hence a loop has to be set up in the NFA.