Coupon Accepted Successfully!


Regular Expression


The regular expressions are useful for representing certain sets of string in an algebraic fashion. Formal definition of regular expressions is as follows:–

Any terminal symbol, i.e. symbols Σ including ^ and φ are regular expression. When, we view 857.png in Σ as 862.png regular expression, we denote it by 867.png

  1. The union of two regular expressions R1 and R2 written as R1 + R2 also a regular expression.
  2. 3. The concatenation of two regular expressions R1 and R2 written as R1 R2 is also a regular expression.
  3. The iteration of a regular expression R, written as R* is also a regular expression.
  4. If R is a regular expression, then (R) is also a regular expression.
  5. The regular expression over Σ are precisely those obtained successively by the application of the rules 1 to 5 once or several times.

Any regular expression can be converted into a finite automation that recognizes the language, it describes and vice versa. Some basic conversions from regular expression to finite automation (M) are shown below:–

  • If r = ε, M is


  • If r = φ, M is 877.png
  • If r = {a} for some a  Σ, M is


  • If r = r1 + r2, then M is


  • If r = r1 . r2, then M is


  • If r = r1, then M is


Using the above basic rules / examples, any regular expression can be converted into a finite automata.

Properties (Identities) of regular expression

  1. 903.png+ R = R
  2. 908.pngR + R913.png = 918.png 
  3. ^R = R ^ = R
  4. ^ * = ^ and 923.png* = ^
  5. R + R = R
  6. R * R * = R *
  7. RR * = R * R
  8. (R*)* = R*
  9. ^ + RR * = ^ + R * R = R*
  10. (PQ) * P = P (QP) *
  11. (P + Q)* = (P * Q*) = ( P* + Q*)*
  12. (P + Q) R = PR + QR and R (P + Q) = RP + RQ



Construction of Finite Automata from Regular Expressions

For regular expression (a + b) the FA will be

939.png or 944.png 

For regular expression ab the FA will be


For regular expression a* the FA will be


Test Your Skills Now!
Take a Quiz now
Reviewer Name