Regular expression

Download PDF

Regular expression

A regular expression can be defined as the following properties.

Kleene Star Closure:

Kleene star closure can be shown as

∑    =   Set of Alphabet

∑* =   Set of all combination of sigma alphabet

For the example ∑ and ∑* can be described as following:

∑                     ∑*

{a}                  {a}* = φ, a, aa, aaa, aaaa, aaaaa……..

{ab}                {ab}*= ab, abab, ababab……..

{aa}                 {aa}*= aa, aaaa, aaaaaa……..

Plus Operator:

It is same to the sigma staric but it does not contains the “φ” operator.

{a}₊ = a, aa, aaa, aaaa, aaaaa……

OR Operator:

OR operator have the following properties:


(a+b)* = φ, a, b, aa, ab, bb, aba….

(a+b)+ = a, b, aa, ab, bb, aba….

(a+b)*a+ = ending must be on a that is a, aa, ba, bba, aaa….

  • In Regular expression, we usually use the “*”, “+” operators.
  • One language can contain more than one regular expression.
  • But the one Regular expression can be represent only one language.
  • a(a+)*           language  staring from ä
  • a(a+)*ä language  starting and ending at ä      
  • ((a+b)(a+b)) even string generating language
  • ((a+b)(a+b))*(a+b) odd string generating language.

The rule for descriptive to RE:

The rules for descriptive to RE are as follows:

  • All the strings formed by descriptive way of the language L1 must be contained in the RE way of language L1.
  • Language L upon ∑={a,b} containing double aa

Our result should be aa, aaa, aab, baa, aaaa, aaaab, abaa…..

RE of this language will be in this form (a+b)*aa (a+b)*:

  • Both languages should generate an exact sequence of the alphabet in equivalency.

Moore machine and Mealy machine


Leave a Reply

Please rate us