5. Regular Expressions

16/02/23

tools - grep, sed specify lexical syntax

Denoted	Procedural
RE	DFA, NFA

Example of RE - $(0+11+101*01)*$ $\Sigma=\{0,1\}$

Define RE$\Sigma$ and given $E:RE\Sigma,$ .....

• $∅$ - is a regular expression
• $\epsilon$ - is a regular expression
• $L∅$ = {}
• $L∅$ = $\lambda ?? False$
• $L\epsilon$ = $\{\epsilon\}$
• ??

* just means all of the concatenations

For every $E:RE\Sigma$ we construct an NFA, $N^{RE}E:NFA\Sigma$ such that $L^{RE}E=L^{NFA}(N^{RE}E)$