Regular Expression IN TOC

Regular Expressions are simple expressions that can describe the language that finite automata accept. It is the most efficient method of representing any language. Regular languages are the languages that some regular expressions accept. A regular expression can also be defined as a pattern sequence that defines a string.

To match character combinations in strings, regular expressions are used. The string searching algorithm used this pattern to find operations on a string.

An expression is regular if and only if the following conditions are met:

• ɸ is a regular expression that stands for regular language ɸ.
• ɛ is a regular expression that stands for regular language {ɛ}.
• If a ∈ Σ  (Σ represents the input alphabet), then a is a regular expression in language {a}.
• If a and b are regular expressions, then a + b is a regular expression with the language as {a,b}.
• If a and b are regular expressions, then ab (a and b concatenation) is also regular.
• If a is a regular expression, then a* (0 or more times a) is also regular.

Note that two regular expressions are equivalent if the languages generated by them are the same. For example,(a+b*)* and (a+b)* yield the same language. Every string produced by (a+b*)* is also produced by (a+b)*, and vice versa.

Examples of Regular Expression in TOC

Here * means 0 or more occurrences, and + means one or more occurrences.

• If regular language is  { }, then the regular expression is ϕ.
• If regular language is  {ϵ}, then the regular expression is ϵϵ.
• If regular language is  {r}, then the regular expression is r.
• If regular languages are LR and LS, then the regular expression is R and S.
• If regular language is LR U LS, the regular expression is R+S.
• If regular language is LR.LS, then the regular expression is R.S
• If regular language is LR*, then the regular expression is R*
• If regular language is L+R, then the regular expression is R+

Properties of Regular Expressions using Operators

(a) Union operator satisfies commutative property and associative property.

        a+b=b+a (commutative)

        a+(b+c)=(a+b) +c (associative)

(b) The concatenation operator satisfies associative property but not commutative property

        ab ≠ b.a (not commutative)

        a(b.c) =(a.b).c (associative)

(c) Both left and right distributive properties of concatenation over union hold.

        x (y+z) = (x.y) + (x.z) (Left distribution of. over +)

        (x+y).z =(x.z) + (y.z) (Right distribution of. over +)

(d) Both left and right distributive properties of union over concatenation does not holds.

        a+(b.c) ≠ (a+b).(a+c)

        (ab)+c ≠ (a+c).(b+c)

(e) Union operetor satisfies idempotent property but the concatenation operator does not holds.

        a+az = a (idempotent)

        a.a ≠ a (not idempotent)

(f) Identity property:

        R+∅ = ∅ +R =R  (∅ is identity element with respect to union operation)

        ε . R = R.ε = R (ε is identity element with respect to concatenation)

(g) Annihilator property: RoX = X

        R+Σ* = Σ* (Σ* is annihilator with respect to union operator)

        R. ∅ = ∅  ( ∅ is annihilator with respect to concatenation operator)