Language Associated With Regular Expressions: FIRST SEM. SY. 2008-2009
Language Associated With Regular Expressions: FIRST SEM. SY. 2008-2009
Language Associated With Regular Expressions: FIRST SEM. SY. 2008-2009
Regular Expressions
Rule 2
(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*
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:
Reg Exp:
^ + x + xx + xxx + xxxx + xxxxx
How Hard it is to Understand a Regular Expression
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
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