regular expression

the operators of regular expressions make use of the following 3 operations on languages:

we call them the regular operations, regular languages are closed under each one of them.
[cite:@john_automata_2006 definition 1.23]

regular expressions are defined inductively:

\textsc{BASIS}: the basis consists of three parts:

the constants $\text{[math]}$ and $\text{[math]}$ are regular expressions, denoting the languages $\text{[math]}$ and $\text{[math]}$ , respectively. that is, $\text{[math]}$ , and $\text{[math]}$ .
if $\text{[math]}$ is any symbol, then $\text{[math]}$ is a regular expression. this expression denotes the language $\text{[math]}$ . that is, $\text{[math]}$ . note that we use boldface font to denote an expression corresponding to a symbol. the correspondence, e.g. that $\text{[math]}$ refers to $\text{[math]}$ , should be obvious.
a variable, usually capitalized and italic such as $\text{[math]}$ , is a variable, representing any language.

\textsc{INDUCTION}: there are four parts to the inductive step, one for each of the three operators and one for the introduction of parentheses.

if $\text{[math]}$ and $\text{[math]}$ are regular expressions, then $\text{[math]}$ is a regular expression denoting the union of $\text{[math]}$ and $\text{[math]}$ . that is, $\text{[math]}$ .
if $\text{[math]}$ and $\text{[math]}$ are regular expressions, then $\text{[math]}$ is regular expression denoting the concatenation of $\text{[math]}$ and $\text{[math]}$ . that is, $\text{[math]}$ .
if $\text{[math]}$ is a regular expression, then $\text{[math]}$ is a regular expression, denoting the closure of $\text{[math]}$ . that is, $\text{[math]}$ .
if $\text{[math]}$ is a regular expression, then $\text{[math]}$ , a parenthesized $\text{[math]}$ , is also a regular expression, denoting the same language as $\text{[math]}$ . formally; $\text{[math]}$ .

[cite:@john_automata_2006 section 3.1.2]

for convenience, we let $\text{[math]}$ be a shorthand for $\text{[math]}$ .
the following definition given by [cite:@sipser_comp_2012] is equivalent to john's.

say that $\text{[math]}$ is a regular expression if $\text{[math]}$ is

$\text{[math]}$ for some $\text{[math]}$ in the alphabet $\text{[math]}$ ,
$\text{[math]}$ ,
$\text{[math]}$ ,
$\text{[math]}$ , where $\text{[math]}$ and $\text{[math]}$ are regular expressions,
$\text{[math]}$ , where $\text{[math]}$ and $\text{[math]}$ are regular expressions, or
$\text{[math]}$ , where $\text{[math]}$ is a regular expression.

in items 1 and 2, the regular expressions $\text{[math]}$ and $\text{[math]}$ represent the languages $\text{[math]}$ and $\text{[math]}$ , respectively. in item 3, the regular expression $\text{[math]}$ represents the empty language. in items 4,5, and 6, the expressions represent the languages obtained by taking the union or concatenation of the languages $\text{[math]}$ and $\text{[math]}$ , or the star of language $\text{[math]}$ , respectively.
[cite:@sipser_comp_2012 definition 1.52]

dont confuse the regular expressions $\text{[math]}$ and $\text{[math]}$ . the expression $\text{[math]}$ represents the language containing a single string--namely, the empty string--whereas $\text{[math]}$ represents the language that doesn't contain any strings.
[cite:@sipser_comp_2012 chapter 1 regular languages]

like other algebras, the regular-expression operators have an assumed order of "precedence", which means that óperators are associated with their operands in a particular order. we are familiar with the notion of precedence from ordinary arithmetic expressions. for regular expressions, the following is the order of precedence for the operators:

the star operator is of highest precedence. that is, it applies only to the smallest sequence of symbols to its left that is a well-formed regular expression.
the concatenation operator.
union

of course, sometimes we do not want the grouping in a regular expression to be as required by the precedence of the operators. If so, we are free to use parentheses to group operands exactly as we choose. In addition, there is never anything wrong with putting parentheses around operands that you want to group, even if the desired grouping is implied by the rules of precedence.
[cite:@john_automata_2006 chapter 3.1.3 precedence of regular-expression operators]

for any languages $\text{[math]}$ , the following algebraic properties hold

associativity: $\text{[math]}$ .
associative law for [[blk:1706801265][union]]: $\text{[math]}$ .
associative law for [[blk:1700165265][concatenation]]: $\text{[math]}$ .
$\text{[math]}$ . this law asserts that $\text{[math]}$ is the identity for union.
$\text{[math]}$ . this law asserts that $\text{[math]}$ is the identity for concatenation.
$\text{[math]}$ . this law asserts that $\text{[math]}$ is the annihilator for concatenation.
left [[blk:1663957762][distributive]] law of concatenation over union: $\text{[math]}$ .
right distributive law of concatenation over union: $\text{[math]}$ .
[[blk:1700242159][idempotence]] law for union: $\text{[math]}$ .
$\text{[math]}$ . this law law says that closing an expression that is already closed does not change the language.
$\text{[math]}$ .
$\text{[math]}$ .
$\text{[math]}$ .
$\text{[math]}$ .
$\text{[math]}$ . this rule is really the definition of the $\text{[math]}$ operator.
$\text{[math]}$ .

[cite:@john_automata_2006 chapter 3.4 algebraic laws for regular expressions]

[cite:@john_automata_2006 chapter 3.4.6 discovering laws for regular expressions]

the expression $\text{[math]}$ denotes strings over $\text{[math]}$ that end with $\text{[math]}$ .
$\text{[math]}$ .
$\text{[math]}$ .
the expression $\text{[math]}$ denotes all the words that include the substring $\text{[math]}$ , i.e. $\text{[math]}$ .
the expression $\text{[math]}$ which is equal to $\text{[math]}$ denotes all the strings over $\text{[math]}$ that dont contain the substring $\text{[math]}$ .

let $\text{[math]}$ be any regular expression, we have the following identities
$\text{[math]}$ however, exchanging $\text{[math]}$ and $\text{[math]}$ in the preceding identities may cause the equalities to fail. $\text{[math]}$ may not equal $\text{[math]}$ . $\text{[math]}$ may not equal $\text{[math]}$ .
[cite:@sipser_comp_2012 section 1.3 regular exxpressions]

a numerical constant that may include a fractional part and/or a sign may be described as a member of the language defined by the regex
$\text{[math]}$ where $\text{[math]}$ is the alphabet of decimal digits. examples of generated strings are: $\text{[math]}$ .
[cite:@sipser_comp_2012 chapter 1 regular languages]

regular expressions and finite automata are equivalent in their descriptive power. this fact is surprising because finite automata and regular expressions superficially appear to be rather different. however, any regular expression can be converted into a finite automaton that recognizes the language it describes, and vice versa.

a language is regular if and only if some regular expression describes it.

[cite:@sipser_comp_2012 chapter 1 regular languages]

automata theory course homework 4 for more practice problems