Single Final State for NFAs Courtesy Costas Busch - RPI 1 Any NFA can be converted to an equivalent NFA with a single final state Courtesy Costas Busch - RPI 2 a Example NFA b a b Equivalent NFA a a b b Courtesy Costas Busch - RPI 3 NFA In General Equivalent NFA Courtesy Costas Busch - RPI Single final state 4 Extreme Case NFA without final state Add a final state Without transitions Courtesy Costas Busch - RPI 5 Properties of Regular Languages Courtesy Costas Busch - RPI 6 For regular languages we will prove that: Union: Concatenation: L1 and L2 L1 L2 L1L2 Star: L1 * Reversal: R L1 Complement: L1 Intersection: L1 L2 Courtesy Costas Busch - RPI Are regular Languages 7 We say: Regular languages are closed under Union: Concatenation: L1 L2 L1L2 Star: L1 * Reversal: R L1 Complement: L1 Intersection: L1 L2 Courtesy Costas Busch - RPI 8 Regular language L1 LM1 L1 NFA Regular language L2 LM 2 L2 NFA M1 Single final state M2 Single final state Courtesy Costas Busch - RPI 9 Example n0 L1 {a b} n M1 a b M2 L2 ba b Courtesy Costas Busch - RPI a 10 NFA for L1 L2 Union M1 M2 Courtesy Costas Busch - RPI 11 Example NFA for L1 L2 {a b} {ba} n L1 {a b} n a b L2 {ba} b a Courtesy Costas Busch - RPI 12 Concatenation NFA for L1L2 M1 M2 Courtesy Costas Busch - RPI 13 Example NFA for L1L2 {a b}{ba} {a bba} n L1 {a b} n n L2 {ba} a b b Courtesy Costas Busch - RPI a 14 Star Operation NFA for L1 * L1 * M1 Courtesy Costas Busch - RPI 15 Example NFA for w w1w2 wk L1* {a b} * n wi L1 L1 {a b} n a b Courtesy Costas Busch - RPI 16 Reverse R NFA for L1 L1 M1 M1 1. Reverse all transitions 2. Make initial state final state and vice versa Courtesy Costas Busch - RPI 17 Example M1 a L1 {a b} n b a R L1 {ba } n M1 b Courtesy Costas Busch - RPI 18 Complement L1 M1 L1 M1 1. Take the DFA that accepts L1 2. Make final states non-final, and vice-versa Courtesy Costas Busch - RPI 19 Example M1 a, b a L1 {a b} n b L1 {a, b} * {a b} n a, b M1 a, b a b Courtesy Costas Busch - RPI a, b 20 Intersection DeMorgan’s Law: L1 L2 L1 L2 L1 , L2 regular L1 , L2 regular L1 L2 regular L1 L2 regular L1 L2 regular Courtesy Costas Busch - RPI 21 Example L1 {a b} regular n L2 {ab, ba} regular Courtesy Costas Busch - RPI L1 L2 {ab} regular 22 Regular Expressions Courtesy Costas Busch - RPI 23 Regular Expressions Regular expressions describe regular languages Example: ( a b c) * describes the language a, bc* , a, bc, aa, abc, bca,... Courtesy Costas Busch - RPI 24 Recursive Definition Primitive regular expressions: Given regular expressions r1 , , and r2 r1 r2 r1 r2 r1 * Are regular expressions r1 Courtesy Costas Busch - RPI 25 Examples A regular expression: a b c * (c ) Not a regular expression: Courtesy Costas Busch - RPI a b 26 Languages of Regular Expressions L r : language of regular expression r Example L(a b c) * , a, bc, aa, abc, bca,... Courtesy Costas Busch - RPI 27 Definition For primitive regular expressions: L L La a Courtesy Costas Busch - RPI 28 Definition (continued) For regular expressions r1 and r2 Lr1 r2 Lr1 Lr2 Lr1 r2 Lr1 Lr2 Lr1 * Lr1 * Lr1 Lr1 Courtesy Costas Busch - RPI 29 Example Regular expression: a b a * La b a * La b La * La b La * La Lb La * a b a * a, b , a, aa, aaa,... a, aa, aaa,..., b, ba, baa,... Courtesy Costas Busch - RPI 30 Example Regular expression r a b * a bb Lr a, bb, aa, abb, ba, bbb,... Courtesy Costas Busch - RPI 31 Example Regular expression Lr {a b r aa * bb * b 2n 2m b : n, m 0} Courtesy Costas Busch - RPI 32 Example Regular expression r (0 1) * 00 (0 1) * L(r ) = { all strings with at least two consecutive 0 } Courtesy Costas Busch - RPI 33 Example Regular expression r (1 01) * (0 ) L(r ) = { all strings without two consecutive 0 } Courtesy Costas Busch - RPI 34 Equivalent Regular Expressions Definition: Regular expressions are equivalent if r1 and r2 L(r1) L(r2 ) Courtesy Costas Busch - RPI 35 Example L = { all strings without two consecutive 0 } r1 (1 01) * (0 ) r2 (1* 011*) * (0 ) 1* (0 ) L(r1) L(r2 ) L and r2 are equivalent regular expr. r1 Courtesy Costas Busch - RPI 36 Regular Expressions and Regular Languages Courtesy Costas Busch - RPI 37 Theorem Languages Generated by Regular Expressions Courtesy Costas Busch - RPI Regular Languages 38 Theorem - Part 1 Languages Generated by Regular Expressions Regular Languages 1. For any regular expression r the language L(r ) is regular Courtesy Costas Busch - RPI 39 Theorem - Part 2 Languages Generated by Regular Expressions Regular Languages 2. For any regular language L there is a regular expression r with L(r ) L Courtesy Costas Busch - RPI 40 Proof - Part 1 1. For any regular expression r the language L(r ) is regular Proof by induction on the size of Courtesy Costas Busch - RPI r 41 Induction Basis Primitive Regular Expressions: , , NFAs L( M1 ) L() L( M 2 ) {} L( ) a regular languages L( M 3 ) {a} L(a) Courtesy Costas Busch - RPI 42 Inductive Hypothesis Assume for regular expressions r1 and r2 that L(r1) and L(r2 ) are regular languages Courtesy Costas Busch - RPI 43 Inductive Step We will prove: Lr1 r2 Lr1 r2 Lr1 * Are regular Languages Lr1 Courtesy Costas Busch - RPI 44 By definition of regular expressions: Lr1 r2 Lr1 Lr2 Lr1 r2 Lr1 Lr2 Lr1 * Lr1 * Lr1 Lr1 Courtesy Costas Busch - RPI 45 By inductive hypothesis we know: L(r1) and L(r2 ) are regular languages We also know: Regular languages are closed under: Union Lr1 Lr2 Concatenation Lr1 Lr2 Star Lr1 * Courtesy Costas Busch - RPI 46 Therefore: Lr1 r2 Lr1 Lr2 Lr1 r2 Lr1 Lr2 Are regular languages Lr1 * Lr1 * Courtesy Costas Busch - RPI 47 And trivially: L((r1)) is a regular language Courtesy Costas Busch - RPI 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 Courtesy Costas Busch - RPI 49 Since L is regular take the NFA M that accepts it L( M ) L Single final state Courtesy Costas Busch - RPI 50 From M construct the equivalent Generalized Transition Graph in which transition labels are regular expressions Example: M a c a c ab a, b Courtesy Costas Busch - RPI 51 Another Example: a q0 b b q1 a, b q2 b b b a q0 q1 a b q2 b Courtesy Costas Busch - RPI 52 Reducing the states: b a q0 b q1 a b q2 b bb * a q0 b bb * (a b) Courtesy Costas Busch - RPI 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 Courtesy Costas Busch - RPI 54 In General e g d Removing states: qi c qj q a b f ae * d ce * b * d* d g ce ce qi f aeae * b* b Courtesy Costas Busch - RPI qj 55 The final transition graph: r4 r1 r3 q0 r2 qf The resulting regular expression: r (r1 r2 r4 * r3 ) * r2 r4 * r r1 * r2 (r4 r3r1 * r2 ) * L( r ) L( M ) L Courtesy Costas Busch - RPI 56 Theorem If L L(A) for some DFA A Then there is a regular expression R such that L L(R) Proof: (by induction on the size of R) Let A’s states be {1, 2, …, n} for some integer n Construct a collection of regular expressions that describe progressively broader sets of paths in DFA A 57 Let Rij(k ) be the regex that represent the set of strings w such that w is the label of a path from state i to j in A, and that path has no intermediate state who’s label is greater than k. Note: beginning & end points, i.e. i & j are not intermediate so they can be greater than k Courtesy Costas Busch - RPI 58 Inductive Definition Basis: k = 0 Since all states are >= 1, restriction on the paths is that the path must have no intermediate states at all. • If i ≠ j An arc from i to j ( 0) •Depending of the DFA A Rij may be φ, a or ( 0) ij R a1 a2 am (If there are m symbols that label arcs from i to j) 59 Inductive Definition •If i = j all loops from i to itself legal paths of length 0 ( 0) ij R a1 a2 am (If there are m symbols that label arcs from i to i) 60 Inductive Definition Induction: Suppose that there is a path from i to j that goes through no state with label higher than k. Consider two cases •path does not go thru state k at all. j i (k ) ij R ( k 1) ij R 61 •path goes thru state k at least once - once More than once i k k ( k 1) ik (k ) ij R ( k 1) kj ( k 1) * kk R (R ( k 1) ij R ( k 1) ik R j k R ) ( k 1) * kk (R ( k 1) kj )R 62

Descargar
# Languages and Finite Automata