Lecture 10 (RLs and CFLs), 2/22/06

Concepts, definitions (in italics):

• Left- and right- most derivations.
• CFGs for arithmetic expressions: ambiguous, non-ambiguous.
• Ambiguous grammar for a language L vs. inherently ambiguous language.
• If two grammars share variables, we can rename the variables for one or both of the grammars so the variables are disjoint.
• Theorem: If Language L is Regular, then L is Context Free
• Converting a regular expression to an equivalent CFG
• Corollary: the class of RLs is a strict subset of the class of CFLs
• The concept of a normal form.
• Chomsky Normal Form for a CFG

Reading:

• Chapter 2.1 to end. (Note: the theorem is not there, it's left as an exersize)
• Homework 5

Skills:

• Know new definitions, understand new concepts.
• Given a parse tree, find a right- or a left- most derivation corresponding to this tree.
• Fix an ambiguous grammar for expressions involving operator precedence and evaluation order.
• Given CFGs G₁ and G₂, construct a CFG G₀ such that L(G₀) = L(G₁) U L(G₂)
• Given CFGs G₁ and G₂, construct a CFG G₀ such that L(G₀) = L(G₁) o L(G₂)
• Given CFGs G₁ and G₂, construct a CFG G₀ such that L(G₀) = L(G₁)*
• Given a RE, create an equivalent CFG.
• Given a CFG G, determine if it is in Chomsky normal form.
• Converting a CFG to one where the start symbol does not appear on the right of any rule
• Converting a CFG to one where the right-hand side of any rule is never longer than two symbols (terminal or non-terminal)
• Given a CFG G, rewrite it so it's in Chomsky normal form.

Notes:

• String generation is top-down while parsing is usually bottom-up
• Multiple derivations may correspond to a parse tree, but there is exactly one rightmost, and one leftmost among them.
• It is possible to root a parse tree at any variable of G. This will generate strings, but not necessarily those in L(G).
• To show that a CFG G is ambiguous, find a string in L(G) which has two distinct parse trees in G.

• The names of CFG variables are meaningless, can always replace any name by a different (new) name without changing the language of the grammar -- like local variables in a procedure.

• Each of the three constructions (see "skills") involves making the variables disjoint, then creating a new start state and adding one or two new rules involving this state and the original start states of G₁ and G₂.

• There are five steps to converting a CFG to Chomsky Normal Form:
  (a) Make sure the start symbol does not appear on the right (we learned last time how to do that).
  (b) Get rid of rules with epsilon on right-hand-side
  (c) Get rid of rules with single variable on right-hand-side
  (d) Get rid of rules with RHS of length >= 2 (we learned last time how to do that).
  (e) Get rid of terminal symbols from rules with RHS of length = 2
  
• Note that each subsequent step in the conversion above preserves the properties of Chomsky Normal Form that were ensured by earlier steps.