Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | |||
|
regular_expression [2009/09/14 00:48] vkuncak |
regular_expression [2014/09/19 12:16] (current) vkuncak |
||
|---|---|---|---|
| Line 3: | Line 3: | ||
| Regular expressions are expressions denoting certain [[strings and languages|languages]]. They are precisely those languages that can be built from the singleton languages $\{\epsilon\}$, and $\{a\}$ for each $a \in \Sigma$, using operations union ($\cup$), concatenation (${\cdot}$), and iteration ($*$) on languages. | Regular expressions are expressions denoting certain [[strings and languages|languages]]. They are precisely those languages that can be built from the singleton languages $\{\epsilon\}$, and $\{a\}$ for each $a \in \Sigma$, using operations union ($\cup$), concatenation (${\cdot}$), and iteration ($*$) on languages. | ||
| - | In regular expressions, $\cup$ is typically denoted $+$ (sometimes $|$), and the curly braces around singleton sets are omitted, so the language $\{a\}$ for $a \in \Sigma$ is denoted simply $a$ and the language $\{\epsilon\}$ by $\epsilon$. The concatenation operator is simply omitted. We next make this more precise. We write $L(r)$ to denote the set that denotes the meaning of a regular expression. | + | In regular expressions, $\cup$ is typically denoted $|$ (sometimes $+$), and the curly braces around singleton sets are omitted, so the language $\{a\}$ for $a \in \Sigma$ is denoted simply $a$ and the language $\{\epsilon\}$ by $\epsilon$. The concatenation operator is simply omitted. We next make this more precise. We write $L(r)$ to denote the set that denotes the meaning of a regular expression. |
| A **regular expression** over alphabet $\Sigma$ is given by: | A **regular expression** over alphabet $\Sigma$ is given by: | ||
| Line 9: | Line 9: | ||
| * $\epsilon$ is a regular expression $L(\epsilon) = \{\epsilon\}$ | * $\epsilon$ is a regular expression $L(\epsilon) = \{\epsilon\}$ | ||
| * if $a \in \Sigma$, then $a$ is a regular expression $L(a) = \{a\}$ | * if $a \in \Sigma$, then $a$ is a regular expression $L(a) = \{a\}$ | ||
| - | * if $r_1$ and $r_2$ are regular expressions, so are $r_1 r_2$, $r_1 + r_2$, and $r_1*$; we define $L(r_1 r_2) = L(r_1) \cdot L(r_2)$, $L(r_1 + r_2) = L(r_1) \cup L(r_2)$, $L(r_1*) = L(r_1)^*$ | + | * if $r_1$ and $r_2$ are regular expressions, so are $r_1 r_2$, $r_1 + r_2$, and $r_1*$; we define $L(r_1 r_2) = L(r_1) \cdot L(r_2)$, $L(r_1 | r_2) = L(r_1) \cup L(r_2)$, $L(r_1*) = L(r_1)^*$ |
| * every regular expression is obtained by a finite number of applications of the rules above. | * every regular expression is obtained by a finite number of applications of the rules above. | ||