Regular expressions
Regular expressions can be seen as a parallel to arithmetic expressions.
-
is an expression whose symbols represent numbers (e.g. natural numbers) and as a whole represents another number, 32. is an expression involving [...] and as a whole represents [...].
A regular expression
- a symbol
for some in an alphabet , where and are regular expressions , where and are regular expressions , where is a regular expression
A regular expression is said to represent a language according to the
rules below. We write
- From item 1, the regular expression
represents the language . - From item 2, the regular expression
represents the language . - From item 3, the regular expression
represents [...]. - From item 4 & 5, the regular expression
and represent the languages obtained by taking the union and concatenation of the languages represented by and . - From item 6, the regular expression
represents the star of the language represented by .
We say that two regular expressions
This definition is lacking in how it describes 'represents'. Maybe it is a function. I think it's coverage of equality is just sufficient, as it delegates the well defined formulation of set equality.
vs
The regular expression
Precedence order
Star has highest precedence, followed by concatenation, with union last.
Shorthand
Two identities
If