# Differences

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

 regular_expression [2009/09/14 00:48]vkuncak regular_expression [2014/09/19 12:16] (current)vkuncak Both sides previous revision Previous revision 2014/09/19 12:16 vkuncak 2009/09/14 00:48 vkuncak 2009/09/14 00:47 vkuncak 2009/09/14 00:47 vkuncak 2008/09/10 10:07 vkuncak 2008/09/10 10:06 vkuncak 2008/09/09 21:56 vkuncak 2008/03/31 21:12 vkuncak 2008/03/31 21:11 vkuncak 2007/05/05 19:32 vkuncak 2007/05/05 19:31 vkuncak 2007/05/05 19:28 vkuncak 2007/05/05 19:28 vkuncak 2007/05/05 19:22 vkuncak 2007/05/05 19:22 vkuncak 2007/05/05 19:19 vkuncak 2007/05/05 19:15 vkuncak 2007/05/05 19:13 vkuncak 2007/05/05 19:13 vkuncak 2007/05/05 19:12 vkuncak 2007/05/05 19:12 vkuncak 2007/05/05 19:11 vkuncak 2007/05/05 19:11 vkuncak 2007/05/05 19:11 vkuncak 2007/05/05 19:10 vkuncak 2007/05/05 18:38 vkuncak created 2014/09/19 12:16 vkuncak 2009/09/14 00:48 vkuncak 2009/09/14 00:47 vkuncak 2009/09/14 00:47 vkuncak 2008/09/10 10:07 vkuncak 2008/09/10 10:06 vkuncak 2008/09/09 21:56 vkuncak 2008/03/31 21:12 vkuncak 2008/03/31 21:11 vkuncak 2007/05/05 19:32 vkuncak 2007/05/05 19:31 vkuncak 2007/05/05 19:28 vkuncak 2007/05/05 19:28 vkuncak 2007/05/05 19:22 vkuncak 2007/05/05 19:22 vkuncak 2007/05/05 19:19 vkuncak 2007/05/05 19:15 vkuncak 2007/05/05 19:13 vkuncak 2007/05/05 19:13 vkuncak 2007/05/05 19:12 vkuncak 2007/05/05 19:12 vkuncak 2007/05/05 19:11 vkuncak 2007/05/05 19:11 vkuncak 2007/05/05 19:11 vkuncak 2007/05/05 19:10 vkuncak 2007/05/05 18:38 vkuncak created 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.