Regular Expresion

Rpegular Expressions
Regular expressions can be used to define languages. A regular expression is like a "pattern"; strings that match the pattern are in the language, strings that do not match the pattern are not in the language.
The construction of regular expressions is defined recursively, starting with primitive regular expressions, which can be composed using typical operators to form more complex regular expressions.
Definition of Regular Expressions
Let ? be a given alphabet.
• ?, ?, a, for a?? are (primitive) regular expressions.

If r, r1, r2 are regular expressions, then
• r* star closure
• r1 + r2 union
• r1 • r2 concatenation
are regular expressions.


Equivalence of FA and RE
For every regular expression there is an equivalence NFA with ?-moves
a* = zero or more of a’s
a+ = one or more of a’s
Rpegular Expressions
Regular expressions can be used to define languages. A regular expression is like a "pattern"; strings that match the pattern are in the language, strings that do not match the pattern are not in the language.
The construction of regular expressions is defined recursively, starting with primitive regular expressions, which can be composed using typical operators to form more complex regular expressions.
Definition of Regular Expressions
Let ? be a given alphabet.
• ?, ?, a, for a?? are (primitive) regular expressions.

If r, r1, r2 are regular expressions, then
• r* star closure
• r1 + r2 union
• r1 • r2 concatenation
are regular expressions.


Equivalence of FA and RE
For every regular expression there is an equivalence NFA with ?-moves
a* = zero or more of a’s
a+ = one or more of a’s

The expression r may be ?, ?, or a for some a in ?, the NFA with ?-moves are

Rpegular Expressions
Regular expressions can be used to define languages. A regular expression is like a "pattern"; strings that match the pattern are in the language, strings that do not match the pattern are not in the language.
The construction of regular expressions is defined recursively, starting with primitive regular expressions, which can be composed using typical operators to form more complex regular expressions.
Definition of Regular Expressions
Let ? be a given alphabet.
• ?, ?, a, for a?? are (primitive) regular expressions.

If r, r1, r2 are regular expressions, then
• r* star closure
• r1 + r2 union
• r1 • r2 concatenation
are regular expressions.


Equivalence of FA and RE
For every regular expression there is an equivalence NFA with ?-moves
a* = zero or more of a’s
a+ = one or more of a’s

The expression r may be ?, ?, or a for some a in ?, the NFA with ?-moves are



The expression r may be ?, ?, or a for some a in ?, the NFA with ?-moves are