Lecture 13 (Non-context-free Languages), 10/11/17

Concepts, definitions (in italics):

         Role of stack characters in transformation from PDAs to CFGs: they allowed us to pair up transitions for rules of type 2, but they cannot appear in the rules (why?)

         Chomsky Normal Form how deep is the tree for string of length n (length of longest derivation is 2n-1, did this for homework)

         Pumping Lemma for CFLs (p. 125)

o    uses a CFG in Chomsky normal form, so all internal nodes have 2 children except for those at lowest level (which have 1)

o    tree terms: depth, subtree rooted at node X

         Negation of PL property

o    Converse of PL

o    Contrapositive of PL

         Note: Converse of PL is not true; some non-CF languages also obey CF property

         We can use the Pumping Lemma for CFLs (actually, its contrapositive) to show that the following languages are not context-free:

         Teaching moment: for L2, w = 0p 1 0p 1 does not work, but w = 0p 1p 0p 1p does

         Note: the intersection of regular and context-free language is context free

o    Given a DFA M1 and a PDA M2, we can create a new PDA that accepts the intersection of L(M1) and L(M2), whose states are pairs of states from M1 and M2 respectively

o    Example: L1 = {w in {a,b,c}* where #as = #bs = #cs}; L2 = an bn cn is the intersection of L0 = a* b* c* and L1. Since L0 is regular but L2 is not CF, L1 is not CF

Reading:

Skills:

         Know new definitions, understand new concepts.

         Understand the Pumping Lemma for CFLs

         Be able to apply either the pumping lemma or the closure rules to show that a language is not regular