Lab for Automated Reasoning and Analysis LARA

Differences

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

Link to this comparison view

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.
  
 
regular_expression.txt · Last modified: 2014/09/19 12:16 by vkuncak
 
© EPFL 2018 - Legal notice