5.Transforming CFGs (1)§

We use grammars to represent a programming language.
Want to know: Is a given string (or program x) valid
(syntactically correct)?
Same as asking if it is in the language.

We have seen that (with restrictions on form of CFG), we can determine whether

$w$ is in

$L(G)$ in

$2|w|$ rounds, each step adding a terminal or increasing in length.

This works, but it is not fast enough, that is, not linear!

Transforming CFGs (2)

Key question: Are there ways to transform (restrict) CFGs such that

1) We can process efficiently

2) without restricting the power of CFGs

<< What does it mean “without restricting the power of CFGs”? >>

Specifically, we look at restrictions on the right hand side of the production rules.

Need to be able to automatically transform an arbitrary CFG into an equivalent restricted CFG.

Substitution Theorem (1)

Sometimes it is easier to reason about grammars for languages without

$\lambda$ .

(Besides, its pointless to keep expanding on productions that derive to the empty string.)

Useful note: It would be easy to add

$\lambda$ to any grammar by adding a new start symbol

$S_0$ ,

$S_0 \rightarrow S \mid \lambda$

So in practice, if we can transform grammar

$G$ into

$\hat{G}$ such that

$L(\hat{G}) = L(G) - \{\lambda\}$ , then the two are effectively equivalent.

Substitution Theorem (2)

Let

$G$ be a CFG. Suppose

$G$ contains

$A \rightarrow x_1Bx_2$

where

$x_i \in (V \cup T)^{*}$ ,

$A$ and

$B$ are different variables, and

$B$ has the productions

$B \rightarrow y_1 \mid y_2 \mid \ldots \mid y_n$ .

We can construct

$G'$ from

$G$ by deleting

$A \rightarrow x_1Bx_2$

from

$P$ and adding to it

$A \rightarrow x_1y_1x_2 \mid x_1y_2x_2 \mid \ldots \mid x_1y_nx_2$ .

Substitution Theorem:

$L(G) = L(G')$ .

Substitution Theorem Example

Grammar

$G$ :

$A \rightarrow a \mid aaA \mid abBc$

$B \rightarrow abbA \mid b$

Substitute to get

$\hat{G}$ :

$A \rightarrow a \mid aaA \mid ab\color{red}{abbA}c \mid ab\color{red}{b}c$

$B \rightarrow abbA \mid b$

Then the B productions become useless productions.

<< Question: Why don’t we also delete $B$ rules? >>

Substitution Theorem Example

What was the point to this? Look at derivations.

Derivation under

$G$ for

$aaabbc$ :

$A \Rightarrow aaA \Rightarrow aaabBc \Rightarrow aaabbc$

Derivation under

$\hat{G}$ for

$aaabbc$ :

$A \Rightarrow aaA \Rightarrow aaabbc$

Useless Productions (1)

We left in the productions for

$B$ , but maybe there is no way remaining to reach them. In that situation, they can go.

This example is not as obvious: (What is wrong with the A production?)

$S \rightarrow aSb \mid \lambda \mid A$

$A \rightarrow aA$

Definition: Variable

$A \in V$ is said to be useful if and only if there is at least one

$w \in L(G)$ such that

$S \stackrel{*} \Rightarrow xAy \stackrel{*} \Rightarrow w$

We want to eliminate both types of useless production (ones that can’t be reached, and ones that don’t terminate).

Theorem: (useless productions)

Let

$G$ be a CFG.

Then there exists

$\hat{G}$ that does not contain any useless variables or productions such that

$L(G) = L(\hat{G})$ .

Process (1)

To Remove Useless Productions:

Let $G = (V,T,S,P)$ .

I. Compute

$V_1 =$ {Variables that can derive strings of terminals}

$V_1 = \emptyset$

2. Repeat until no more variables added

* For every

$A \in V$ with

$A \rightarrow x_1x_2\ldots x_n$ , all

$x_i \in (T^* \cup V_1)$ , add

$A$ to

$V_1$

3. Take

$P_1$ as all productions in

$P$ whose symbols are all in

$(V_1 \cup T)$

Then

$G_1 = (V_1, T, S, P_1)$ has no variables that can’t derive strings.

NOTE: Now need to get rid of productions we can’t use.

Example (1)

S→aB∣bA
A→aA
B→Sa∣b
C→cBc∣a
D→bCb
E→Aa∣b

We process this to eliminate

$A$ :

B, C, and E all have productions with just terminals, so they go into

$V_1$ .

Now, D has a production with just symbols that are terminals or variables already in

$V_1$ , so it goes into

$V_1$ .

Process (2)

II. Draw Variable Dependency Graph

For A→xBy, draw A→B.
Make A and B be nodes with an arc from
A to B.
Remove productions for V if there is no path from S to
V in the dependency graph.
Resulting Grammar G′ is such that L(G)=L(G′) and
G′ has no useless productions.

Example (2)

S→aB
B→Sa∣b
C→cBc∣a
D→bCb
E→b

Example (3)

$G'$ :

$S \rightarrow aB$

$B \rightarrow Sa \mid b$

Removing $\lambda$ Productions

NOTE: Last time talked about simpler CFG that had no $\lambda$ productions, now we will show how to get rid of them.

Theorem (remove λ productions)
Let G be a CFG with λ not in L(G).
Then there exists a CFG G′ having no
λ productions such that L(G)=L(G′).

Process: Removing $\lambda$ Productions

1. Let

$V_n = \{A \mid \exists\ \mbox{production}\ A \rightarrow \lambda\}$

2. Repeat until no more additions

* if

$B \rightarrow A_1A_2 \ldots A_m$ and

$A_i \in V_n$ for all

$i$ , then put

$B$ in

$V_n$

THUS,

$V_n = \{A \mid A\stackrel{*}{\Rightarrow} \lambda \}$

3. Construct

$G'$ with productions

$P'$ such that

* If

$A \rightarrow x_1x_2\ldots x_m \in P, m \ge 1$ , then put all productions formed when

$x_j$ is replaced by

$\lambda$ (for all

$x_j \in V_n$ ) such that

$|\mbox{rhs}| \ge 1$ into

$P'$ .

Example: Step 2

S→Ab
A→BCB∣Aa
B→b∣λ
C→cC∣λ

2. Repeat until no more additions

* if

$B \rightarrow A_1A_2 \ldots A_m$ and

$A_i \in V_n$ for all

$i$ , then put

$B$ in

$V_n$

THUS,

$V_n = \{A \mid A\stackrel{*}{\Rightarrow} \lambda \}$

Which variables can derive

$\lambda$ ?

B and C directly

A indirectly (because BCB can become

$\lambda$ )

Example: Step 3

3. Construct

$G'$ with productions

$P'$ such that

* If

$A \rightarrow x_1x_2\ldots x_m \in P, m \ge 1$ , then put all productions formed when

$x_j$ is replaced by

$\lambda$ (for all

$x_j \in V_n$ ) such that

$|\mbox{rhs}| \ge 1$ into

$P'$ .

$G'$ :

S→Ab∣b
A→BCB∣BC∣BB∣CB∣B∣C∣Aa∣a
B→b
C→cC∣c

NOTE: Don’t add $A \rightarrow \lambda$ !

Unit Productions

Definition: Unit Production:

$A \rightarrow B$

where

$A, B \in V$ .

Consider removing unit productions: Suppose we have

$A \rightarrow B$

$B \rightarrow a \mid ab$

This becomes: $A \rightarrow a \mid ab$

Unit Productions (2)

But what if we have

A→B becomes A→C
B→CB→A
C→AC→B

But we didn’t get rid of unit productions!

Removing Unit Productions

Theorem (Remove unit productions)
Let G=(V,T,S,P) be a CFG without
λ productions.
Then there exists CFG G′=(V′,T′,S,P′) that does not
have any unit productions and L(G)=L(G′).

Process

1. Find for each

$A$ , all

$B$ such that

$A \stackrel{*}{\Rightarrow} B$

(Draw a dependency graph showing relationship of Unit productions.

Make a node for each variable. For any rule

$A \Rightarrow B$ , draw an arc from

$A$ to

$B$ .)

2. Construct

$G' = (V', T', S, P')$ by

(a) Put all non-unit productions in

$P'$

(b) For all

$A \stackrel{*}{\Rightarrow} B$ such that

$B \rightarrow y_1 \mid y_2 \mid \ldots y_n \in P'$ , put

$A \rightarrow y_1 \mid y_2 \mid \ldots y_n \in P'$

Run DFS with

$A$ as root.

Note the star in

$A \stackrel{*}{\Rightarrow} B$

Never put a unit production in

$P'$ .

Example (1)

Original:

S→Aa∣B
B→A∣bb
A→a∣bc∣B

Unit Production Dependency Graph:

Example (2)

Remove the unit production rules, and add these rules:

S→a∣bc∣bb
A→bb
B→a∣bc

Result:

S→a∣bc∣bb∣Aa
A→a∣bb∣bc
B→a∣bb∣bc

Theorem

Theorem: Let

$L$ be a CFL that does not contain

$\lambda$ . Then there exists a CFG for

$L$ that does not have any useless productions,

$\lambda$ productions, or unit productions.

Proof:

Remove λ productions
Remove unit productions
Remove useless productions

Order is important. Removing

$\lambda$ productions can create unit productions!

Chomsky Normal Form (CNF)

Definition: A CFG is in Chomsky Normal Form (CNF) if all productions are of the form

$A \rightarrow BC$ or

$A \rightarrow a$

where

$A, B, C \in V$ and

$a \in T$ .

Why would you want to put a grammar in this form?

Because it is easier to work with (reason about), so will see it in future.

Theorem:

Any CFG $G$ with $\lambda$ not in $L(G)$ has an equivalent grammar in CNF.

Proof:

1. Remove

$\lambda$ productions, unit productions, and useless productions. (We already know how to do this.)

2. For every right-hand-side of length

$> 1$ , replace each terminal

$x_i$ by a new variable

$C_j$ and add the production

$C_j \rightarrow x_i$ .

Note: All productions are in the correct form or the right-hand-side is a string of variables.

3. Replace every right-hand-side of length

$> 2$ by a series of productions, each with right-hand-side of length 2.

Example (1)

S→CBcd
B→b
C→Cc∣e

(after removing λ, usless, unit productions:)
S→CBC1C2
B→b
C→CC3∣e
C1→c
C2→d
C3→c

Example (2)

(after step 2):
S→CZ1
Z1→BZ2
Z2→C1C2
B→b
C→CC3∣e
C1→c
C2→d
C3→c

Greibach Normal Form (GNF)

Definition: A CFG is in Greibach normal form (GNF) if all productions have the form

$A \rightarrow ax$

where

$a \in T$ and

$x \in V^*$

This is like an s-grammar (or simple grammar), except the s-grammar definition includes a further restriction that any pair $(A, a)$ can occur at most in one rule.

This is so that you wouldn’t have to backtrack (only one choice to match the derivation of a string). So it is very restrictive.

GNF Theorem

For every CFG

$G$ , there exists a grammar in GNF.

See proof in modules.

Example:

S→AB
A→aA∣bB∣b
B→b

Simple substitutions give us:

S→aAB∣bBB∣bB
A→aA∣bB∣b
B→b

What You Should Know

Know what usless productions, unit productions, etc. are
Don’t memorize the processes for eliminating them, but
understand how they work in principle.
Know what the GNF and CNF forms are.

5.Transforming CFGs (1)§

Transforming CFGs (2)

Substitution Theorem (1)

Substitution Theorem (2)

Substitution Theorem Example

Substitution Theorem Example

Useless Productions (1)

Theorem: (useless productions)

Process (1)

Example (1)

Process (2)

Example (2)

Example (3)

Removing λ\lambda Productions

Process: Removing λ\lambda Productions

Example: Step 2

Example: Step 3

Unit Productions

Unit Productions (2)

Removing Unit Productions

Process

Example (1)

Example (2)

Theorem

Chomsky Normal Form (CNF)

Theorem:

Example (1)

Example (2)

Greibach Normal Form (GNF)

GNF Theorem

What You Should Know

Removing $\lambda$ Productions

Process: Removing $\lambda$ Productions