Simplifying a Grammar, Two: Null Productions

Get access to whole semester resourcesSemester Pass

Chapter Forty-Six

Syllabus topic Module 1, "Context Free Languages: CFG simplification"

Pages 227 to 231 of 438

In one line

A null production is one whose right hand side is empty, and it can be removed by adding, for every production, the variants with the nullable symbols left out.

In the wording a student can write in an examination: a production of the form A to epsilon is called a null or epsilon production. A variable A is nullable if A derives epsilon in zero or more steps. Given a context free grammar G, a grammar without null productions generating L(G) minus the empty string is obtained by replacing every production with all the versions of it in which any subset of its nullable symbols is omitted, discarding those whose right hand side becomes empty, and deleting the null productions.

Why remove them

Because the normal forms of chapters 48 and 49 have no room for them. Chomsky normal form allows a right hand side of exactly two variables or exactly one terminal, and epsilon is neither. So the conversion cannot begin until the null productions are gone.

And because they are what makes the CYK algorithm of chapter 51 and the pushdown construction of chapter 58 work: both rely on every step of a derivation making the string longer or consuming a symbol, and a null production makes a step that does neither.

The one thing that is lost

A grammar with no null productions cannot generate the empty string, since every derivation from S produces at least one terminal.

So if epsilon is in L(G), it cannot be in the language of the simplified grammar. The standard remedy is to add a fresh start symbol:

S0->S | ε

with S0 the new start symbol and S the old one, and with S0 appearing on no right hand side. That single null production is then the only one in the grammar, it is on the start symbol alone, and chapter 26 noted that type 1 grammars allow exactly that exception for exactly this reason.

The convention in this chapter, and in most textbooks, is to remove the null productions first and add the fresh start symbol afterwards if the empty string is wanted. A question asking for the removal expects the first part; a question asking for an equivalent grammar expects both.

Finding the nullable variables

An upward closure, the same shape as chapter 45's generating test.

Mark every variable having the production A to epsilon.
Repeatedly, mark any variable having a production whose right hand side consists only of marked variables.
Stop when nothing new is marked.

Step 2 is the step that is forgotten. A variable with no epsilon production of its own can still be nullable: if B is nullable and C is nullable then A to BC makes A nullable, because both can vanish.

Simplifying a Grammar, Two: Null Productions

The replacement

For each production, look at which symbols on its right hand side are nullable. Then write out every version of the production obtained by omitting some subset of those occurrences, including the empty subset, which is the production itself.

Two rules govern it.

Discard a version whose right hand side becomes empty. That would be a new null production, which defeats the purpose. The only exception is the fresh start symbol above.

Each occurrence is decided separately. If A to BB and B is nullable, the versions are A to BB, A to B taking the first out, A to B taking the second out, and A to nothing, which is discarded. The two middle versions are the same production, so it is written once: a grammar is a set of productions and duplicates collapse.

A production with k nullable occurrences gives 2 to the k versions before discarding, which is chapter 2's count of subsets and is why the grammar can grow.

Worked example 1

S->ABaC
A->BC
B->b | ε
C->D | ε
D->d

Accepts: a, ba, bba, ad, bad, da, bdbad

Rejects: ε, b, d, ab, dab, badd

Step 1: the nullable variables.

Pass 1. B has B to epsilon, so B is nullable. C has C to epsilon, so C is nullable.

Pass 2. A has A to BC, and both B and C are now marked, so A is nullable. D has only D to d, so not. S has S to ABaC, which contains the terminal a, so S is not nullable however nullable the variables are.

Pass 3 marks nothing new. Nullable: A, B, C.

Step 2: the replacement, production by production.

S to ABaC. Three nullable occurrences: A, B and C. So 2 to the 3, that is 8 versions:

Omit	Version
nothing	S to ABaC
A	S to BaC
B	S to AaC
C	S to ABa
A and B	S to aC
A and C	S to Aa
B and C	S to Aa... no: omitting B and C from ABaC leaves S to Aa
A, B and C	S to a

Eight versions and one duplicate pair in the listing above, so seven distinct productions for S. None is empty, because the terminal a is always there.

A to BC. Both occurrences nullable, so four versions: A to BC, A to C, A to B, and A to nothing. The last is discarded.

B to b. No nullable occurrence, so it stands. B to epsilon is deleted.

C to D. D is not nullable, so it stands. C to epsilon is deleted.

Simplifying a Grammar, Two: Null Productions

D to d. Stands.

The result:

S->ABaC | BaC | AaC | ABa | aC | Aa | a
A->BC | B | C
B->b
C->D
D->d

Accepts: a, ba, bba, ad, bad, da, bdbad

Rejects: ε, b, d, ab, dab, badd

L(Z2) = L(Z1)

The original grammar does not generate epsilon, because S to ABaC always leaves the terminal a, so nothing is lost and the two languages are exactly equal, which the checker decides.

Seven productions for S where there was one. That growth is normal and is the price of the normal forms.

Worked example 2, where the empty string is in the language

S->aSb | ε

Accepts: ε, ab, aabb, aaabbb

Rejects: a, b, ba, aab

Nullable: S, from S to epsilon. Nothing else, there being nothing else.

The replacement. S to aSb has one nullable occurrence, S, so two versions: S to aSb and S to ab. Neither is empty. And S to epsilon is deleted.

S->aSb | ab

Accepts: ab, aabb, aaabbb

Rejects: ε, a, b, ba, aab

L(Z4) = L(Z4R)

S->aSb | ab

The language is now a to the n followed by b to the n for n at least 1, and the empty string is gone. That is correct and expected.

To get it back, add the fresh start symbol:

S0->S | ε
S->aSb | ab

Accepts: ε, ab, aabb, aaabbb

Rejects: a, b, ba, aab

L(Z5) = L(Z3)

Now the language is exactly the original one, and the grammar has exactly one null production, on a start symbol appearing on no right hand side. The checker decides that equality, so the remedy is verified rather than asserted.

The three errors

Missing a nullable variable. A variable with no epsilon production of its own can be nullable through its productions. Step 2 of the closure is not optional.

Keeping a version whose right hand side is empty. That reintroduces a null production and the grammar is not simplified.

Forgetting the empty string. If epsilon was in the language it is not any more, and a question asking for an equivalent grammar wants the fresh start symbol.

Distinctions

	A null production	A nullable variable
Is	a production A to epsilon	a variable deriving epsilon in any number of steps
Found by	reading the grammar	an upward closure
Every one is	on a nullable variable	not necessarily the subject of a null production

	Removing null productions	Adding the fresh start symbol
Effect on the language	removes the empty string, if it was there	puts it back
Number of null productions after	zero	exactly one, on the start symbol
Needed for chapters 48 and 49	yes	the single exception is tolerated

Simplifying a Grammar, Two: Null Productions

What it does NOT mean

Nullable does not mean having a null production. A derives epsilon through A to BC when B and C are both nullable, without A having a null production of its own.

The replacement does not delete the original production. It keeps it and adds the shortened versions, unless the original was itself null.

Removing null productions does not preserve the language exactly when epsilon is in it. It removes epsilon, and the fresh start symbol is how it is restored.

Two identical versions are one production. A grammar is a set of productions, so duplicates from the replacement collapse.

The grammar gets bigger, and that is not a fault. A production with k nullable occurrences gives up to 2 to the k versions.

Quick revision

A null production is A to epsilon. A variable is nullable when it derives epsilon in any number of steps.
Find the nullable variables by an upward closure: mark those with a null production, then any whose right hand side

is entirely marked variables, and repeat.

For each production, add every version omitting some subset of its nullable occurrences; discard a version whose

right hand side is empty; then delete the null productions.

A production with k nullable occurrences gives up to 2 to the k versions, and duplicates collapse.
The empty string is lost. Restore it with a fresh start symbol S0 to S or epsilon, with S0 on no right hand side.
This is a prerequisite for chapters 48 and 49, not a polish.

Test yourself

1. Define nullable, and give a variable that is nullable without having a null production. A variable is nullable if it derives epsilon in zero or more steps. In S->AB, A->ε, B->ε, the variable S is nullable through S to AB, and has no null production of its own.

2. Remove the null productions from S->ABC, A->a | ε, B->b | ε, C->c. Nullable: A and B. S to ABC has two nullable occurrences, giving S to ABC, S to BC, S to AC and S to C. Then A to a, B to b and C to c stand, and the two null productions are deleted.

3. How many versions does a production with 3 nullable occurrences give, and how many survive? Eight, being the subsets of three occurrences. All survive unless one has an empty right hand side, which happens only when every symbol of the production is nullable.

4. What happens to the empty string, and how is it restored? It leaves the language, because no derivation can now produce nothing. Add a fresh start symbol S0 with the productions S0 to S and S0 to epsilon, and make sure S0 appears on no right hand side.

Simplifying a Grammar, Two: Null Productions

5. Why must a version with an empty right hand side be discarded? Because it is itself a null production, which is what the step exists to remove. The only tolerated null production is the one on the fresh start symbol.

6. Why is this step needed before Chomsky normal form? Because that form permits a right hand side of exactly two variables or exactly one terminal, and epsilon is neither, so a grammar with null productions cannot be put into it.

The rest of this subject

These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.

Issue