RS#2 - The class of context free languages (CFL) Examples PDA - describe CFLs Diagrams CFG - describe CFLs Conversion to PDA (Loop Construction) Conversion to Chomsky Normal Form Derivation, Parse tree Ambiguity, Inherently ambiguous languages For CFG and PDA: Creating from a language description Discerning language from each Prove a language is a CFL (by doing one of these) Understanding the stack, and matching nature Some languages are not CFL: pumping lemma for CFL languages -using to prove a language is not a CFL -understanding the pigeonhole and loop idea closure for CFLs -Kleene operators -not closed under intersection tightest classification: three classifications: -regular (just show it is regular) -CFL but not regular (prove not regular and show it is a CFL) -not a CFL (show it is not a CFL)