Single Final State for NFA Fall 2004 COMP 335 1 Any NFA can be converted to an equivalent NFA with a single final state Fall 2004 COMP 335 2 a Example

a b NFA b a a b Fall 2004 Equivalent NFA b COMP 335

3 NFA In General Equivalent NFA Fall 2004 COMP 335 Single final state 4 Extreme Case

NFA without final state Add a final state Without transitions Fall 2004 COMP 335 5 Properties of Regular Languages Fall 2004 COMP 335 6

For regular languages L1 andL2 we will prove that: Union: Concatenation: Star: Reversal: L1 L2 L1L2 L1 * R L1 Complement: L1 Intersection: L1 L2

Fall 2004 COMP 335 Are regular Languages 7 e say: Regular languages are closed unde Union: Concatenation: Star: Reversal: L1 L2 L1L2 L1 * R

L1 Complement: L1 Intersection: L1 L2 Fall 2004 COMP 335 8 Regular language L1 Regular languageL2

L M1 L1 NFA M1 Single final state Fall 2004 L M 2 L2 NFA M2 Single final state COMP 335 9 Example

n L1 {a b : n 0} M1 a b M2 L2 ba Fall 2004 b COMP 335 a 10

Union NFA for L1 L2 M1 Fall 2004 M2 COMP 335 11

Example NFA for n L1 L2 {a b : n 0} {ba} n L1 {a b} a b

L2 {ba} b Fall 2004 a COMP 335 12 Concatenation NFA for L1L2 M1 M2

Fall 2004 COMP 335 13 Example NFA for a n L1 L2 {a b : n 0}{ba} {a bba : n 0} M1 b

Fall 2004 n M2 b COMP 335 a 14 NFA for

Star Operation L1 * L1 * M1 Fall 2004 COMP 335 15 Example

NFA for w w1w2 wk n L1* {a b : n 0} * wi L1 a M1 b

Fall 2004 COMP 335 16 Reverse NFA for L1 L1 R M1 M1

1. Reverse all transitions 2. Make initial state final state and vice versa Fall 2004 COMP 335 17 Example a n b L1 {a b : n 0} a

R M1 M1 b n L 1 {ba : n 0} Fall 2004 COMP 335 18 Complement L1

M1 L1 M1 1. Take the DFA that acceptsL1 2. Make final states non-final, and vice-versa Fall 2004 COMP 335 19 Example M1

a, b a b n L1 {a b : n 0} a, b M1 n L1 {a, b} * {a b} Fall 2004

a, b a b COMP 335 a, b 20 Intersection DeMorgans Law: Fall 2004 L1 L2 L1 L2 L1 , L2 regular

L1 , L2 regular L1 L2 regular L1 L2 regular L1 L2 regular COMP 335 21

Example n L1 {a b : n 0} regular L1 L2 {ab} L2 {ab, ba} regular Fall 2004 COMP 335 regular 22 Regular Expressions Fall 2004

COMP 335 23 Regular Expressions Regular expressions describe regular languages Example: (a b c) * describes the language a, bc Fall 2004

* , a, bc, aa, abc, bca,... COMP 335 24 Recursive Definition Primitive regular expressions: , , Given regular expressions r1 andr2 r1 r2 r1 r2 r1 * Are regular expressions

r1 Fall 2004 COMP 335 25 Examples A regular expression: a b c * (c ) Not a regular expression: Fall 2004 COMP 335 a b 26

Languages of Regular Expressions L r : language of regular expression r Example: L(a b c) , a, bc, aa, abc, bca,... * Fall 2004 COMP 335 27 Definition For primitive regular expressions : L

L L a a Fall 2004 COMP 335 28 Definition (continued) r2 For regular expressionsr1 and L r1 r2 L r1 L r2 L r1 r2 L r1 L r2 L r1 L r1 * 1

L r L r1 Fall 2004 COMP 335 * 29 Example Regular expression: a b a * L a b a * L a b L a L a b L a

* * L a L b L a a b a * * a, b , a, aa, aaa,... a, aa, aaa,..., b, ba, baa,... Fall 2004 COMP 335 30

Example * Regular expression r a b a bb L r a, bb, aa, abb, ba, bbb,... Fall 2004 COMP 335 31 Example * * Regular expression r aa bb b

2n 2m L r {a b Fall 2004 b : n, m 0} COMP 335 32 Example * Regular expression r (0 1) 00 (0 1) * L(r )= {all strings with at least

two consecutive 0} Fall 2004 COMP 335 33 Example * Regular expressionr (1 01) (0 ) L(r )= { all strings without two consecutive 0 } Fall 2004 COMP 335

34 Equivalent Regular Expressions Definition: Regular expressionsr1 andr2 are equivalent ifL( r1 ) L( r2 ) Fall 2004 COMP 335 35 Example L= { all strings without two consecutive 0 }

* r1 (1 01) (0 ) * * * * r2 (1 011 ) (0 ) 1 (0 ) r1 L(r1 ) L(r2 ) L Fall 2004 and r2

are equivalent Reg. expressions COMP 335 36 Regular Expressions and Regular Languages Fall 2004 COMP 335 37 Theorem Languages Generated by Regular Expressions

Fall 2004 COMP 335 Regular Languages 38 Theorem - Part 1 Languages Generated by Regular Expressions 1.

Regular Languages For any regular expressionr the language L (r ) is regular Fall 2004 COMP 335 39 Theorem - Part 2 Languages Generated by Regular Expressions 2.

Regular Languages For any regular language L , there is a regular expression r with L( r ) L Fall 2004 COMP 335 40 Proof - Part 1 1. For any regular expressionr the language L (r ) is regular

Proof by induction on the size of r Fall 2004 COMP 335 41 Induction Basis , Primitive Regular Expressions: , NFAs L( M1 ) L( ) L( M 2 ) {} L( )

a Fall 2004 regular languages L( M 3 ) {a} L(a ) COMP 335 42 Inductive Hypothesis Assume for regular expressionsr1 that L( r1 ) and L( r2 ) are regular languages Fall 2004 COMP 335

r2 and 43 Inductive Step We will prove: L r1 r2 L r1 r2 * 1 Lr are regular Languages.

L r1 Fall 2004 COMP 335 44 By definition of regular expressions: L r1 r2 L r1 L r2 L r1 r2 L r1 L r2 * 1 L r L r1 *

L r1 L r1 Fall 2004 COMP 335 45 By inductive hypothesis we know: L(r1 )and L(r2 ) are regular languages We also know: Regular languages are closed under: L r1 L r2 Union Concatenation Star Fall 2004 L r1 L r2

L r1 * COMP 335 46 Therefore: L r1 r2 L r1 L r2 L r1 r2 L r1 L r2 Are regular languages L r1 * L r1 * Fall 2004 COMP 335 47

And trivially: L((r1 )) Fall 2004 is a regular language COMP 335 48 Proof Part 2 2. For any regular language L there is a regular expression r with L( r ) L

Proof by construction of regular expression Fall 2004 COMP 335 49 Since L is regular, take an NFA M that accepts it L ( M ) L Single final state Fall 2004 COMP 335 50

From M , construct an equivalent Generalized Transition Graph in which transition labels are regular expressions Example: M a c a a, b Fall 2004 c a b COMP 335

51 Another Example: q0 a b b q1 a, b q2 b b

b q0 a q1 a b q2 b Fall 2004 COMP 335 52 Reducing the states: a

q0 b b q1 a b q2 b bb * a q0 Fall 2004 b bb * (a b) COMP 335 q2

53 Resulting Regular Expression: bb * a q0 b bb * (a b) q2 r (bb * a ) * bb * (a b)b * L ( r ) L ( M ) L Fall 2004 COMP 335 54

In General e Removing states: d qi c qj q a b ae * d ce * b ce * d qi

Fall 2004 ae * b COMP 335 qj 55 The final transition graph: r1 q0 r4 r3 r2

qf The resulting regular expression: * 1 2 * * 3 1 2 r r r (r4 r r r ) L ( r ) L ( M ) L Fall 2004 COMP 335 56