Essays /

13 Regular Expressions Essay

Essay preview

Regular Expressions

This ppt is the work by Dr. Costas Busch, used with permission, and available from
http://csc.lsu.edu/~busch/courses/theorycomp/fall2008/
1

Regular Expressions
Regular expressions
describe regular languages

Example:

(a  b c) *
describes the language

 a, bc *   , a, bc, aa, abc, bca,...
2

Recursive Definition
Primitive regular expressions:  ,  , 
Given regular expressionsr1

r2
and

r1  r2
r1 r2
r1 *

Are regular expressions

 r1 
3

Examples
A regular expression:

 a  b c  * (c   )

Not a regular expression:

 a  b 

4

Languages of Regular Expressions

L r 

r
: language of regular expression

Example

L (a  b c) *   , a, bc, aa, abc, bca,...

5

Definition
For primitive regular expressions:
L   
L     
L a   a

6

Definition (continued)
For regular expressionsr1

andr2

L r1  r2  L r1   L r2 
L r1 r2  L r1  L r2 
L r1 *  L r1   *
L  r1   L r1 
7

Example
Regular expression: a  b  a *

L  a  b  a * ...

Read more

Keywords

/~busch/courses/theorycomp/fall2008/ 0 00 01 011 1 10 11 12 13 14 15 16 17 18 19 2 20 21 22 23 24 25 26 27 28 29 2m 2n 3 30 31 32 33 34 35 4 5 6 7 8 9 aa aaa abb abc accept acceptsl ae also andr2 anoth augment avail b ba baa basi bb bbb bc bca busch c ce close closur concaten construct contain continu convert correspond costa csc.lsu.edu csc.lsu.edu/~busch/courses/theorycomp/fall2008/ d definit describ dfa dfas dr e end equival exampl express expressionr expressionsr1 final general generat given graph hypothesi ifl induct initi know l label languag languagel left link m m1 m2 mean n nfa nfam nfas ofr oper part permiss ppt primit process proof proof-part prove q q0 q1 q2 qf qi qj r r1 r2 r3 r3r1 r4 recurs reduc regular remov repeat represent result say sinc singl size standard star state step string substr suppos take theorem therefor transit trivial two union use withl without work