Language Associated With Regular Expressions: FIRST SEM. SY. 2008-2009

Download as ppt, pdf, or txt
Download as ppt, pdf, or txt
You are on page 1of 12

Language Associated with

Regular Expressions

AUTOMATA AND LANGUAGE THEORY

FIRST SEM. SY. 2008-2009


 We are now ready to give the rules for associating a language
with every regular expression. As we might suspect, the
method for doing this is given recursively.
Definition

 The following ruled define the language associated with any


regular expression:
Rule 1:

The Language associate with the regular expression that is just a


single letter is that one-letter word alone and the language
associated with ^ is just {^}, a one-word language.
Definition

Rule 2

If r1 is a regular expression associated with the language L1 and


r2 is a regular expression associated with the Language L2, then:

(i) The regular expression (r1) (r2) is associated with the L1L2 that is
the language L1 times L2 language(r1r2) = L1L2
(ii) The regular expression r1+r2 is associated with the language
formed by the union of the set L1 and L2:

language(r1+r2) = L1+L2
Definition

(ii) The language associated with the regular expression (r1)* is L1*,
the Kleen closure of the set L1 as a set of words:
language(r1*) = L1*

 One again, this collection of rules proves recursively that there


is some language associated with every regular expression.
 As we build up a regular expression from the rules, we
simultaneously are building up the corresponding language.
Finite Language are Regular

Theorem
If L is finite language (a language with only finite many words),
then L can be defined by a regular expression. In other words, all
finite language are regular
Finite Language are Regular

Proof
 Language:L = {baa abbba bababa}
 The regular expression of that language:

baa + abbba + bababa

 Language:L = {aa ab ba bb}


 Reg. Exp:
aa+ab+ba+bb
(a+b)(a+b)
 Language:
L = {^ x xx xxx xxxx xxxxx}

 Reg Exp:
^ + x + xx + xxx + xxxx + xxxxx
How Hard it is to Understand a Regular Expression

 Let us Examine some regular expression and se if we are lucky


enough to understand something about the language they
represent.

 Example:
 Consider (a+b)*(aa+bb)(a+b)*
• How ca you describe the regular expression?
• What strings are not covered by this expression?
• How would you express that expression?
How Hard it is to Understand a Regular Expression

Combining the two gives


 (a+b)*(aa+bb)(a+b)* + (^+b)(ab)*(^+a)

• This expression defines all things

 Consider
E = (a+b)* a (a+b)* (a+^) (a+b)* a (a+b)*
E = (a+b)* a (a+b)* a (a+b)* a (a+b)* +
(a+b)* a (a+b)* ^ (a+b)* a (a+b)*
E = (a+b)* a (a+b)* a (a+b)* a (a+b)* +
(a+b)* a (a+b)* a (a+b)*
E = (a+b)* a (a+b)* a (a+b)*
How Hard it is to Understand a Regular Expression

It is possible by repeated application of the rules for forming


regular expressions to produce an expression in which the star
operator is applied to a subexpression that already has a star in it
Examples
 (a+b*)*
 (aa+ab*)*
• In (a+b*)*, the internal * adds nothing to the language since
possible strings of a’s and b’s are described by both expressions.
(a+b*)* = (a+b)*
• Also, in accordance with the theorem 1, (a*)* = a*
• Is (aa+ab*)* ≠ or = (aa + ab)* (explain why?)
 Now, try to evaluate: ((a+bbba*) + ba*b)*
How Hard it is to Understand a Regular Expression

Prove that (a*b*)* = (a+b)*


 The language defined by this expression can be made up of factors of
the form a*b*, but since both the single a and the single b are words
form in a*b*, this language contains all strings of a’s and b’s. it cannot
contain more than everything

You might also like