ZeePedia

Null Production

<< Total language tree, Regular Grammar
Chomsky Normal Form (CNF) >>
img
Theory of Automata
(CS402)
Theory of Automata
Lecture N0. 35
Reading Material
Introduction to Computer Theory
Chapter 13
Summary
Examples of building TG's corresponding to the Regular Grammar, Null productions with examples, Nullable
productions with examples, Unit production with example, Chomsky Normal Form (Definition)
Example
Consider the following CFG
S Æ aA|bB
A Æ aS|a
B Æ bS|b
A
then the corresponding TG will be
a
a
a
+
S-
b
b
b
B
+
The corresponding RE may be (aa+bb) .
Example
Consider the following CFG
S Æ aaS|bbS|abX|baX|L
X Æ aaX|bbX|abS|baS,
aa,bb
aa,bb
then the corresponding TG will be
ab,ba
L
X
+
S-
ab,ba
The corresponding language is EVEN-EVEN.
Null Production
Definition
The production of the form nonterminal Æ L is said to be null production.
Example: Consider the CFG, S Æ aA|bB|L, A Æ aa|L, B Æ aS
Here S Æ L and A Æ L are null productions.
Note
If a CFG has a null production, then it is possible to construct another CFG without null production accepting
the same language with the exception of the word L i.e. if the language contains the word L then the new
language cannot have the word L.
Following is a method to construct a CFG without null production for a given CFG
Method
Delete all the Null productions and add new productions e.g.
consider the productions of a certain CFG  X Æ aNbNa, N Æ L, delete the production N Æ L and using the
production X Æ aNbNa, add the new productions X Æ aNba, X Æ abNa and X Æ aba
Thus the new CFG will contain the productions X Æ aNba|abNa|aba|aNbNa
Note: It is to be noted that X Æ aNbNa will still be included in the new CFG.
Nullable Production
104
img
Theory of Automata
(CS402)
Definition
A production is called nullable production if it is of the form N Æ L
or
there is a derivation that starts at N and leads to L i.e. N1 Æ N2, N2 Æ N3, N3 Æ N4, ..., Nn ÆL, where N, N1, N2,
..., Nn are non terminals.
Example
Consider the following CFG
S Æ AA|bB, A Æ aa|B, B Æ aS | L
Here S Æ AA and A Æ B are nullable productions, while B Æ L is null a production.
Following is an example describing the method to convert the given CFG containing null productions and
nullable productions into the one without null productions
Example
Consider the following CFG
S Æ XaY|YY|aX|ZYX
X Æ Za|bZ|ZZ|Yb
Y Æ Ya|XY|L
Z Æ aX|YYY
It is to be noted that in the given CFG, the productions S Æ YY, X Æ ZZ, Z Æ YYY are Nullable productions,
while Y Æ L is Null production.
Here the method of removing null productions, as discussed earlier, will be used along with replacing
nonterminals corresponding to nullable productions like nonterminals for null productions are replaced.
Thus the required CFG will be
S ÆXaY|Xa|aY|a|YY|Y|aX|ZYX|YX|ZX|ZY
X Æ Za|a|bZ|b|ZZ|Z|Yb
Y Æ Ya|a|XY|X|Y
Z Æ aX|a|YYY|YY|Y
Example
Consider the following CFG
S Æ XY, X Æ Zb, Y Æ bW
Z Æ AB, W Æ Z, A Æ aA|bA|L
B ÆBa|Bb|L.
Here A Æ L and B Æ L are null productions, while Z Æ AB, W Æ Z are nullable productions. The new CFG
after, applying the method, will be
S Æ XY
X Æ Zb|b
Y Æ bW|b
Z Æ AB|A|B
WÆZ
A Æ aA|a|bA|b
B ÆBa|a|Bb|b
Note
While adding new productions all Nullable productions should be handled with care. All Nullable productions
will be used to add new productions, but only the Null production will be deleted.
Unit production
The productions of the form nonterminal Æ one nonterminal, is called the unit production.
Following is an example showing how to eliminate the unit productions from a given CFG.
Example
Consider the following CFG
S Æ A|bb
A Æ B|b
B Æ S|a
Separate the unit productions from the nonunit productions as shown below
105
img
Theory of Automata
(CS402)
unit prods.
nonunit prods.
SÆA
S Æ bb
AÆB
AÆb
BÆS
BÆa
S Æ A gives S Æ b
(using A Æ b)
S Æ A Æ B gives S Æ a
(using B Æ a)
A Æ B gives A Æ a
(using B Æ a)
A Æ B Æ S gives A Æ bb
(using S Æ bb)
B Æ S gives B Æ bb
(using S Æ bb)
B Æ S Æ A gives B Æ b
(using A Æ b)
Thus the new CFG will be
S Æ a|b|bb, A Æ a|b|bb, B Æ a|b|bb.
Which generates the finite language {a,b,bb}.
Chomsky Normal Form
If a CFG has only productions of the form
nonterminal Æ string of two nonterminals
or
nonterminal Æ one terminal
then the CFG is said to be in Chomsky Normal Form (CNF).
106
Table of Contents:
  1. What does automata mean, Introduction to languages
  2. Kleene Star Closure, Recursive definition of languages
  3. Regular Expression, Recursive definition of Regular Expression
  4. Equivalent Regular Expressions
  5. Finite Automaton
  6. Equivalent FAs
  7. FA corresponding to finite languages
  8. Examples of TGs: accepting all strings
  9. Generalized Transition Graphs
  10. Nondeterminism, Kleene’s Theorem
  11. Proof(Kleene’s Theorem Part II)
  12. Kleene’s Theorem Part III
  13. Concatenation of FAs
  14. Closure of an FA
  15. Nondeterministic Finite Automaton, Converting an FA to an equivalent NFA
  16. NFA with Null String
  17. NFA and Kleene’s Theorem
  18. NFA corresponding to Concatenation of FAs
  19. Distinguishable strings and Indistinguishable strings
  20. Finite Automaton with output, Moore machine
  21. Mealy machine
  22. Equivalent machines
  23. Mealy machines in terms of sequential circuit
  24. Regular languages, Complement of a language
  25. Nonregular languages
  26. Pumping Lemma
  27. Pumping Lemma version II
  28. Pseudo theorem
  29. Decidability
  30. finiteness of a language
  31. Context Free Grammar (CFG), CFG terminologies
  32. Trees
  33. Polish Notation (o-o-o)
  34. Total language tree, Regular Grammar
  35. Null Production
  36. Chomsky Normal Form (CNF)
  37. A new format for FAs
  38. Nondeterministic PDA
  39. PDA corresponding to CFG
  40. Conversion form of PDA
  41. Conversion Form, Joints of the machine
  42. Row language, Nonterminals
  43. Non-Context-Free language, Pumping lemma for CFLs
  44. Decidablity, Parsing Techniques
  45. Turing machine