• English only

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

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.

regular_expression.txt · Last modified: 2014/09/19 12:16 by vkuncak

© EPFL 2018 - Legal notice