Automata Theory Tutorial on Regular Expressions
a regular expression can be recursively defined as follows −
ε is a regular expression indicates the language containing an empty string. (l (ε) = {ε})
φ is a regular expression denoting an empty language. (l (φ) = { })
x is a regular expression where l = {x}
-
if x is a regular expression denoting the language l(x) and y is a regular expression denoting the language l(y), then
x + y is a regular expression corresponding to the language l(x) ∪ l(y) where l(x+y) = l(x) ∪ l(y).
x . y is a regular expression corresponding to the language l(x) . l(y) where l(x.y) = l(x) . l(y)
r* is a regular expression corresponding to the language l(r*)where l(r*) = (l(r))*
if we apply any of the rules several times from 1 to 5, they are regular expressions.
some re examples
| regular expressions | regular set |
|---|---|
| (0 + 10*) | l = { 0, 1, 10, 100, 1000, 10000, … } |
| (0*10*) | l = {1, 01, 10, 010, 0010, …} |
| (0 + ε)(1 + ε) | l = {ε, 0, 1, 01} |
| (a+b)* | set of strings of a’s and b’s of any length including the null string. so l = { ε, a, b, aa , ab , bb , ba, aaa…….} |
| (a+b)*abb | set of strings of a’s and b’s ending with the string abb. so l = {abb, aabb, babb, aaabb, ababb, …………..} |
| (11)* | set consisting of even number of 1’s including empty string, so l= {ε, 11, 1111, 111111, ……….} |
| (aa)*(bb)*b | set of strings consisting of even number of a’s followed by odd number of b’s , so l = {b, aab, aabbb, aabbbbb, aaaab, aaaabbb, …………..} |
| (aa + ab + ba + bb)* | string of a’s and b’s of even length can be obtained by concatenating any combination of the strings aa, ab, ba and bb including null, so l = {aa, ab, ba, bb, aaab, aaba, …………..} |