Header Ads Widget

Regular expression

Regular expression

  • Regular expression is a sequence of pattern that defines a string. It is used to denote regular languages.
  • It is also used to match character combinations in strings. String searching algorithm used this pattern to find the operations on string.
  • In regular expression, x* means zero or more occurrence of x. It can generate {e, x, xx, xxx, xxxx,.....}
  • In regular expression, x+ means one or more occurrence of x. It can generate {x, xx, xxx, xxxx,.....}

Operations on Regular Language

The various operations on regular language are:

Union: If L and M are two regular languages then their union L U M is also a union.

L U M = {s | s is in L or s is in M} 


Intersection: If L and M are two regular languages then their intersection is also an intersection.

L ⋂ M = {st | s is in L and t is in M}  


Kleene closure: If L is a regular language then its kleene closure L1* will also be a regular language.

L* = Zero or more occurrence of language L.


Example

Write the regular expression for the language:

L = {abn w:n ≥ 3, w ∈ (a,b)+}


Solution:

The string of language L starts with "a" followed by atleast three b's. Itcontains atleast one "a" or one "b" that is string are like abbba, abbbbbba, abbbbbbbb, abbbb.....a

So regular expression is:

r= ab3b* (a+b)+

Here + is a positive closure i.e. (a+b)+ = (a+b)* - ∈


Post a Comment

0 Comments