Context free grammar, Theory of Computation

A context free grammar G = (N, Σ, P, S)  is in binary form if for all productions

A we have |α| ≤ 2. In addition we say that G is in Chomsky Normaml Form (CNF) if it is in binary form and if the only sorts of production have the form

            A → a             (where a is a terminal symbol)

or

            A → BC          (where B and C are non-terminals)

We will show that every CFG G is λ- equivalent to a grammar G' that is in CNF (i.e. the only difference between G and G' is that may or may not be included. Since we know how to test for the presence of in our languages we will be able to construct equivalent grammars.

Posted Date: 3/9/2013 1:45:35 AM | Location : United States







Related Discussions:- Context free grammar, Assignment Help, Ask Question on Context free grammar, Get Answer, Expert's Help, Context free grammar Discussions

Write discussion on Context free grammar
Your posts are moderated
Related Questions
When we study computability we are studying problems in an abstract sense. For example, addition is the problem of, having been given two numbers, returning a third number that is


Different types of applications and numerous programming languages have been developed to make easy the task of writing programs. The assortment of programming languages shows, dif

Construct a Mealy machine that can output EVEN or ODD According to the total no. of 1''s encountered is even or odd.

The Emptiness Problem is the problem of deciding if a given regular language is empty (= ∅). Theorem 4 (Emptiness) The Emptiness Problem for Regular Languages is decidable. P

The universe of strings is a very useful medium for the representation of information as long as there exists a function that provides the interpretation for the information carrie

1. Does above all''s properties can be used to prove a language regular? 2..which of the properties can be used to prove a language regular and which of these not? 3..Identify one

The fact that the Recognition Problem is decidable gives us another algorithm for deciding Emptiness. The pumping lemma tells us that if every string x ∈ L(A) which has length grea

How useful is production function in production planning?