Regular Expression
A Regular Expression can be recursively defined as follows:
1. ε is a Regular Expression indicates the language containing an empty string. (L (ε)
= {ε})
2. φ is a Regular Expression denoting an empty language. (L (φ) = { })
3. x is a Regular Expression where L={x}
4. If X is a Regular Expression denoting the language L(X) and Y is a Regular
Expression denoting the language L(Y), then
(a) X + Y is a Regular Expression corresponding to the language L(X) U L(Y)
where L(X+Y) = L(X) U L(Y).
(b) X . Y is a Regular Expression corresponding to the language L(X) . L(Y)
where L(X.Y)= L(X) . L(Y)
(c) R* is a Regular Expression corresponding to the language L(R*) where
L(R*) = (L(R))*
5. If we apply any of the rules several times from 1 to 5, they are Regular Expressions.
Some RE Examples
No comments:
Post a Comment