L15 Equivalence of FA and RE

Regular 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.
Note: ? = ?
Lec 15 : Computation Theory Equivalence of FA and RE
2
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 :
Regular 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.