Simplification of Context Free Grammar - Automata

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

Useless productions/ Reduced Context Free Grammar

The productions in context free grammar that contains useless symbols are called Useless productions. The grammar that we obtain after deleting useless production rules are called reduced Context Free Grammar. Our main focus is to remove productions and symbols that are never used in any derivation.

Besides this, it may also contain some null production or unit production in context free grammar.

How to eliminate useless productions?

To eliminate useless productions, we apply following two steps:

Step 1: In step1, we will construct a new grammar equivalent to given grammar. Every variable in new grammar derives some terminal string.

Step 2: In step2, we construct a new grammar equivalent to the grammar obtain in step1. Every symbol in new grammar appears in some sentential form.

Example:

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:

In Context Free Grammar, the productions of the form B -> ? are called null productions. It is not always possible to eliminate all null productions in context free grammar because sometimes eliminating all null productions may change the resulting language.

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.

Elimination of Unit Productions/ Removal of unit Production:

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:

If we have following set of production rules:

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

  => D

  => E

  => F

  => G

  => 01

All productions like

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) = 01


Related Topics

Context Free Grammar - Automata

Context Free Grammar Grammar defines a set of rules, and with the help of these rules valid sentences in a language are constructed. A grammar consists of collection of substitution rules,...

3 minutes read.

Chomsky's Normal Form - Automata

Chomsky's Normal Form (CNF) In context free grammar, the left-hand side of production rules contains only one variable, and right side may contain any number of variables or terminals in production...

4 minutes read.

Recursive Language and Recursive Enumerable Language

Recursive Language and Recursive Enumerable Language Before discussing Recursive language and Recursive Enumerable language, let us see what Turing machine responds for some input string. If we have the Turing machine T...

4 minutes read.

Pumping Lemma for Regular Languages - Automata

Pumping Lemma for Regular Languages The language accepted by the finite automata is called Regular Language. If we are given a language L and asked whether it is regular or not?...

4 minutes read.

Derivation Tree of Context Free Grammar - Automata

Derivation Tree of Context Free Grammar Derivation tree gives a way to show how a string can be derived from context free grammar. It is also called as parse tree, production...

3 minutes read.

Minimization of Finite Automata

Minimization of Finite Automata The term minimization refers to the construction of finite automata with a minimum number of states, which is equivalent to the given finite automata. The number of...

4 minutes read.

Automata Regular Expressions

Regular Expressions Regular expressions are also referred as rational expressions, which are used to describe the algebraic description of regular languages. It is generally a sequence of characters that is used...

3 minutes read.

Finite Automata with Output

Finite Automata with Output The Finite State machine is similar to Finite Automata, except that it has the additional capacity of producing output. Finite State machine = Finite Automata + Output Capabilities Types...

3 minutes read.

Non-deterministic Turing Machine - Automata

A non-deterministic Turing machine (NTM) is a theoretical machine used in computability theory to study the extent to which a machine can "guess" at a solution and yet still be...

4 minutes read.

Pumping Lemma for Context Free Languages

Pumping Lemma for Context Free Languages The Pumping Lemma is made up of two words, in which, the word pumping is used to generate many input strings by pushing the symbol...

3 minutes read.

Conversion from Mealy Machine to Moore Machine

Conversion from Mealy Machine to Moore Machine In this topic, we will see different ways that are used for the conversion of Mealy Machine to Moore Machine. Moore Machine The output of Moore...

4 minutes read.

Minimization of Finite Automata with Output

Minimization of Finite Automata with Output The method to minimize the Moore and Mealy machine is very much similar to the method that we have used to minimize the DFA. Methods to...

3 minutes read.

Converting Finite Automata to Regular Expression using Arden’s Theorem

Converting Finite Automata to Regular Expression using Arden’s Theorem The Arden’s Theorem can be applied to find the regular expression recognized by the given transition diagram. This theorem can be applied...

4 minutes read.

Ambiguity in Context Free Grammar - Automata

Ambiguity in Context Free Grammar? Context Free Grammar Context Free Grammar has one condition for production rules, which is, on the left-hand side of each rule, there must be only single variable,...

4 minutes read.

Conversion from NFA to DFA

Conversion from NFA to DFA A Non-deterministic Finite Automata (NFA) is a finite state machine, in which, the move from one state to another is not fully deterministic, i.e., for a...

4 minutes read.

Closure Properties of Regular Languages -Automata

Closure Properties of Regular Languages We use the term “Closure” when we talk about sets of things. If we have two regular languages L1 and L2, and L is obtained by...

3 minutes read.

Equivalence of Regular Grammar and Finite Automata

Equivalence of Regular Grammar and Finite Automata Regular Grammar / type -3 grammar A regular grammar or type-3 defines the language called regular language that is accepted by finite Automata.A Regular Grammar...

3 minutes read.

Automata Chomsky Hierarchy

Chomsky Hierarchy Formal languages: A language with precise syntax and semantics are called formal languages. Noam Chomsky has defined the Chomsky hierarchy in 1956. He is an American scientist and philosopher, and...

3 minutes read.

Finite Automata

Finite Automata Finite state Automata or Finite State Machine is the simplest model used in Automata. Finite state automata accepts regular language. In this, the term finite means it has a...

4 minutes read.

Automata Tutorial

What is Automata? Automata is a mathematical model and abstract model, which is used to detect string in various languages. In Automata, Regular language is recognized by Finite state AutomataContext Free language...

4 minutes read.