6.3.1. Transforming Grammars¶

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 (the membership problem).

Last time we showed that if we could transform a CFG into a CFG with no $\lambda$-productions, and no rules like $A \rightarrow B$, then we could determine if $w$ is in or not in $L(G)$ in $2|w|$ rounds, each step adding a terminal or increasing in length.

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

We will look at lots of methods for transforming grammars. Some will be forms that are easier to work with, some are easier to use in proofs.

1 / 28 Settings

<<<>>>

Now we start our exploration of useful transformations for CFGs.

Saving...
Server Error
Resubmit

6.3.2. Remove Useless Productions¶

1 / 27 Settings

<<<>>>

Previously we raised the question of what to do when some variables cannot ever lead to a useful derivation. This frameset discusses how to recognize and remove useless productions.

1. S
2. →
3. aB

1. S
2. →
3. bA

1. A
2. →
3. aA

1. B
2. →
3. Sa

1. B
2. →
3. b

1. C
2. →
3. cBc

1. C
2. →
3. a

1. D
2. →
3. bCb

1. E
2. →
3. Aa

1. E
2. →
3. b

2. →

1. S
2. →
3. aB

1. B
2. →
3. Sa

1. B
2. →
3. b

1. C
2. →
3. cBc

1. C
2. →
3. a

1. D
2. →
3. bCb

1. E
2. →
3. b

2. →

1. S
2. →
3. aB

1. B
2. →
3. Sa

1. B
2. →
3. b

2. →

1. 0
2. 1
3. 2
4. 3
5. 4
6. 5

$V_1$

S

B

C

D

E

Saving...
Server Error
Resubmit

6.3.3. Remove Lambda Productions¶

1 / 15 Settings

<<<>>>

Previously we saw that we need to remove lambda productions to avoid running into an infinite loop when using brute force expansion of the derivation tree if the string is not in the language of the grammar.

1. S
2. →
3. AcB

1. A
2. →
3. aAa

1. A
2. →
3. λ

1. B
2. →
3. Bbb

1. B
2. →
3. λ

2. →

1. 0
2. 1

$V_n$

2. →

2. →

2. →

2. →

2. →

2. →

2. →

2. →

2. →

Saving...
Server Error
Resubmit

6.3.4. Remove Unit Productions¶

1 / 28 Settings

<<<>>>

Next we will consider Unit Productions. These are productions that simply replace one variable with another, such as $A \Rightarrow B$. When deriving a string, these seem an unnecessary step. Instead of going from $A$ to $B$ and then replacing $B$ with the RHS of one of its rules (such as $B \Rightarrow bb$), we could simply go there directly with a rule like $A \Rightarrow bb$. Of couse, this requires that we also replace every other production that has $B$ on its LHS with an equivalent production that has $A$ on its LHS.

1. S
2. →
3. AB

1. A
2. →
3. B

1. B
2. →
3. Bb

1. B
2. →
3. C

1. C
2. →
3. A

1. C
2. →
3. c

1. C
2. →
3. Da

1. D
2. →
3. A

2. →

1. $S$
2. →
3. $AB$

1. $B$
2. →
3. $Bb$

1. $C$
2. →
3. $c$

1. $C$
2. →
3. $Da$

2. →

2. →

2. →

2. →

2. →

2. →

2. →

2. →

2. →

2. →

S

A

B

C

D

1. $A \stackrel{*}{\Rightarrow} C$0
2. $A \stackrel{*}{\Rightarrow} B$1
3. 2
4. 3
5. 4
6. 5
7. 6
8. 7
9. 8

Saving...
Server Error
Resubmit

6.3.5. Chomsky Normal Form (CNF)¶

1 / 16 Settings

<<<>>>

To summarize what we have done so far: We have found algorithms to remove from any CFG the useless productions, $\lambda$ productions, and unit productions.

1. S
2. →
3. CBcd

1. B
2. →
3. b

1. C
2. →
3. Cc

1. C
2. →
3. e

2. →

2. →

2. →

2. →

2. →

2. →

Saving...
Server Error
Resubmit

6.3.6. Greibach Normal Form (GNF)¶

1 / 21 Settings

<<<>>>

$\textbf{Definition:}$ A CFG is in Greibach normal form (GNF) if all productions are of the form
$A \rightarrow ax$
where $x \in V^*$ and $a \in T$

1. S
2. →
3. AB

1. S
2. →
3. Aa

1. S
2. →
3. b

1. A
2. →
3. cA

1. A
2. →
3. c

1. B
2. →
3. Ad

1. B
2. →
3. e

2. →

2. →

2. →

2. →

2. →

2. →

2. →

Saving...
Server Error
Resubmit