Scribe: Allison Wong

Class Notes From: Thursday, October 18, 2001

Notes cover: I. Parse tree

II Chomsky normal form

III. PDA construction

I. Parse Tree

Let G = (V, S, R, S)

L(G) = {w: S w}

For each derivation S w, we can use a tree to represent the steps. In this tree, the root is S. For each variable A, if A ® u is a rule used in the derivation, write u = u1u2…uk, where each ui is a child of A, and we list these children of A as u1…uk. The leaves are terminals and the leaves from left to right form a string of terminals, which is w. We call w a yield. Such a tree is called a parse tree.

Pg. 95 Ex 2.3

<FACTOR> ® ( <EXPR>) | a

a + a x a

Þ <TERM> + <TERM>

Þ <FACTOR> + <TERM>

Þ a + <TERM>

Þ a + <TERM> x <FACTOR>

Þ a + <FACTOR> x <FACTOR>

Þ a + a x <FACTOR>

Þ a + a x a is a string generated with this grammar.

For every derivation you will have a parse tree and for every parse tree you will get a derivation.

II. Chomsky Normal Form:

On forms of context-free grammar rules.

Let G be a CFG(context-free grammar) if every rule in G has the following form:

A ® BC, where B and C are nonterminals (variables)

not equal to S

A ® a, where a is a terminal

S ® e

Then G is said to be in Chomsky Normal Form.

It makes parsing easier. Any parse tree on Chomsky Normal Form(CNF) is a binary tree. In this tree, every internal node will either have exactly two children as nonterminals or exactly one child as a leaf.

Can we turn an arbitrary CFG into CNF? The answer is yes. There is an algorithm to do the translation.

Alg. (Proof of Thm 2.6)

1. Add a new start symbol So, and add So ® S

2. Take care of e-rules

Suppose A ® e is a rule

First, remove A ® e

Second, if R ® uAv is a rule, add R ® uv. Remember, we do so for each occurrence of A. Hence, if R ® uAvAw is a rule, then we need to add

R ® uvAw, R ® uAvw, R ® uvw.

3. We’ll take care of unit rules ( A ® B)

If A ® B is a rule, remove it. Then whenever a rule B ® u appears, add

A ® u. Keep doing so until no more unit rules are left.

After steps 1, 2, and 3, the rules left have the following form:

A ® w, |w| ³2. (except So ® e) or w is Î S

Let A ® u1u2…uk (k ³ 2) be a remaining rule.

A ® u1A1

A ® u2A2

Ak-1 ® ukAk

For each of these rules, if ui is a terminal, add ui ® ui

Ai-1 ® uiAi remove Ai-1

Read Exercise 2.7

III. Constructing PDA

1. Informal description of a PDA, but the description has to be acceptable by anyone who has some basic training to agree that the description can be turned into a formal definition.

2. Come up with a formal definition if insisted.

Example 2.9 L = {0n1n : n ³ 0 }

Push 0 when 0 is read

Pop when 1 is read

Accept if the stack is empty when the last symbol in the input is read