SIMPLIFICATION OF CONTEXT-FREE GRAMMAR
- Get link
- X
- Other Apps
Simplification of Context Free Grammar
Context Free Grammar has recursive structure. The languages that are accepted with Context Free Grammar are called Context Free Languages. Context Free Grammar has one condition for production rules, i.e., on the left-hand side of each rule, there must be only single variable, and on the right-hand side, there may be combination of variables and terminals including ?.
In Context Free Grammar, sometimes all the productions rules and symbols are not needed for the derivation to solve. Some productions rules are never used during derivation of any string. Elimination of these types of productions or symbols is called Simplification of Context Free Grammar.
We will use the various simple methods to simplify the given context free grammar without changing the resulting language. The following types of productions rules are never used during derivation of any string from context free grammar:
- Useless productions
- Null productions
- Unit productions
How to eliminate useless productions?
S -> ABC|a
A -> b
B -> c
C -> d
E -> e
F -> f
G -> g
--In this grammar G, we have useless productions i.e.
E -> e
F -> f
G -> g
--After eliminating we have reduced grammar whose productions rules are:
S -> ABC|a
A -> b
B -> c
C -> d
Elimination of Null Productions/Removal of Null Production:
Example:
Consider the context free grammar, whose productions are
S -> aS
S -> aA
S -> ?
A -> ?
In these productions, we have two null productions
S -> ? and A -> ?. We can eliminate one production A -> ?, the resulting grammar G1 will be:
S -> aS
S -> aA
S -> ?
This does not change the language defined by given context free grammar. But if we delete S -> ?, then we will be unable to get the language
L (G1) = L (G) = {an | n>=0}
Thus, it is possible to eliminate production A -> ?, but if we eliminate S -> ?, we are unable to generate ? in L (G). We can eliminate all null productions in context free grammar, if ? is not derived by L (G). If ? is in L (G), then G must have some ? productions.
If any given Context free Grammar production in the form of
A -> B
Where A and B are variables, then this type of production is called unit production (or chin rule).
Example:
S -> B
B -> C
C -> D
D -> E
E -> F
F -> G
G -> 01
The language defined by grammar is L (G) = 01.
Solution:
Let us see the derivation of string 01 from given grammar.
S => B => C
=> E
=> F
=> G
=> 01
B -> C
C -> D
D -> E
E -> F
F -> G
G -> 01
Are useful for replacing B with G.
As G -> 01
L (G) = 01
We can write above productions as:
S -> 01
L (G) = 01
Thus we have L (G1) = L (G) = 0
- Get link
- X
- Other Apps
Comments
Post a Comment