6.4.1. Transforming Grammars¶

Programming language developers often use grammars to represent a the syntax for a programming language. Of course, a key question related to implementing a programming language (or any other use of a grammer) is this: Is a given program syntactically correct? This is exactly the same as asking if the string is in the language defined by that grammar (the membership problem).

We have seen that if we could transform a CFG into an equivalent CFG with no $\lambda$-productions, and no rules like $A \rightarrow B$, then we can determine if string $w$ is in or not in $L(G)$ in $2|w|$ derivation rounds, where each step adds a terminal or increases the length of then sentential form of the current derivation. This works, but it is not fast! At least it avoids the possibility of getting into an infinite loop.

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.4.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.4.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.4.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.4.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.4.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