Properties of Context-Free languages Prof. Busch - LSU 1 Union Context-free languages are closed under: Union L1 is context free L1 L 2 L 2 is context free is context-free Prof. Busch - LSU 2 Example Language Grammar n n L1 { a b } L 2 { ww R S1 aS 1b | S 2 aS 2 a | bS 2 b | } Union n n L { a b } { ww R } Prof. Busch - LSU S S1 | S 2 3 In general: For context-free languages L1 , L 2 with context-free grammars G1 , G 2 and start variables S1 , S 2 The grammar of the union L1 L 2 S has new start variable and additional production S S1 | S 2 Prof. Busch - LSU 4 Concatenation Context-free languages Concatenation are closed under: L1 is context free L1 L 2 L 2 is context free is context-free Prof. Busch - LSU 5 Example Language Grammar n n L1 { a b } L 2 { ww R S1 aS 1b | S 2 aS 2 a | bS 2 b | } Concatenation n n L { a b }{ ww R } Prof. Busch - LSU S S1 S 2 6 In general: For context-free languages L1 , L 2 with context-free grammars G1 , G 2 and start variables S1 , S 2 The grammar of the concatenation L1 L 2 S has new start variable and additional production S S1 S 2 Prof. Busch - LSU 7 Star Operation Context-free languages Star-operation are closed under: L is context free * L Prof. Busch - LSU is context-free 8 Example Language Grammar n n S aSb | L {a b } Star Operation n n S1 SS 1 | L {a b } * Prof. Busch - LSU 9 In general: For context-free language with context-free grammar and start variable L G S The grammar of the star operation L * S1 has new start variable and additional production S1 SS 1 | Prof. Busch - LSU 10 Negative Properties of Context-Free Languages Prof. Busch - LSU 11 Intersection Context-free languages intersection are not closed under: L1 is context free L1 L 2 L 2 is context free not necessarily context-free Prof. Busch - LSU 12 Example n n m n m m L1 { a b c } L2 {a b c } Context-free: Context-free: S AC S AB A aAb | A aA | C cC | B bBc | Intersection L1 L 2 { a b c } NOT context-free n n n Prof. Busch - LSU 13 Complement Context-free languages complement are not closed under: L is context free L Prof. Busch - LSU not necessarily context-free 14 Example n n m n m m L1 { a b c } L2 {a b c } Context-free: Context-free: S AC S AB A aAb | A aA | C cC | B bBc | Complement n n n L1 L 2 L1 L 2 { a b c } NOT context-free Prof. Busch - LSU 15 Intersection of Context-free languages and Regular Languages Prof. Busch - LSU 16 The intersection of a context-free language and a regular language is a context-free language L1 context free L1 L 2 L 2 regular context-free Prof. Busch - LSU 17 Machine M 1 Machine M 2 NPDA for L1 DFA for L 2 context-free regular Construct a new NPDA machine M that accepts L1 L 2 M simulates in parallel M 1 and M 2 Prof. Busch - LSU 18 NPDA M 1 q1 a, b c DFA M 2 q2 a p1 transition p2 transition NPDA M q1 , p1 a , b c q , p 2 2 transition Prof. Busch - LSU 19 NPDA M 1 q1 , b c DFA M 2 q2 p1 transition NPDA M q1 , p1 , b c q 2 , p1 transition Prof. Busch - LSU 20 NPDA M 1 DFA M 2 q0 p0 initial state initial state NPDA M q0 , p0 Initial state Prof. Busch - LSU 21 NPDA M 1 DFA M 2 p1 q1 final state p2 final states NPDA M q1 , p1 q1 , p 2 final states Prof. Busch - LSU 22 Example: context-free * * L1 { w1 w 2 : | w1 | | w 2 |, w1 { a , b } , w 2 { c , d } } NPDA M 1 a, 1 b, 1 c ,1 d ,1 q 0 , q1 , q 2 , q 3 Prof. Busch - LSU 23 regular * L 2 { a , c} DFA M 2 a, c p0 Prof. Busch - LSU 24 context-free Automaton for: L1 L 2 { a n c n : n 0} NPDA M a, 1 q0 , p0 , q1 , p 0 c ,1 , Prof. Busch - LSU q2 , p0 , q3 , p0 25 In General: M simulates in parallel M 1 and M 2 M accepts string w if and only if M 1 accepts string w and M 2 accepts string w L(M ) L(M 1) L(M 2 ) Prof. Busch - LSU 26 Therefore: M is NPDA L ( M 1 ) L ( M 2 ) is context-free L1 L 2 is context-free Prof. Busch - LSU 27 Applications of Regular Closure Prof. Busch - LSU 28 The intersection of a context-free language and a regular language is a context-free language Regular Closure L1 context free L1 L 2 L 2 regular context-free Prof. Busch - LSU 29 An Application of Regular Closure Prove that: n n L { a b : n 100 , n 0} is context-free Prof. Busch - LSU 30 We know: n n { a b : n 0} is context-free Prof. Busch - LSU 31 We also know: L1 { a 100 100 b * is regular } L1 {( a b ) } { a 100 100 b Prof. Busch - LSU } is regular 32 n n {a b } context-free * L1 {( a b ) } { a regular n n (regular closure) { a b } L1 n n 100 100 b context-free n n { a b } L1 { a b : n 100 , n 0} L is context-free Prof. Busch - LSU 33 } Another Application of Regular Closure Prove that: L { w : n a nb n c } is not context-free Prof. Busch - LSU 34 If L { w : n a n b n c } is context-free (regular closure) Then n n n L { a * b * c *} { a b c } context-free regular context-free Impossible!!! Therefore, L is not context free Prof. Busch - LSU 35

Descargar
# Languages and Finite Automata