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
design a turing machine that accepts the language which consists of even number of zero''s and even number of one''s?

i have some questions in automata, can you please help me in solving in these questions?

spam messages h= 98%, m= 90%, l= 80% non spam h=12%, m = 8%, l= 5% The organization estimates that 75% of all messages it receives are spam messages. If the cost of not blocking a

What is the Best way to write algorithm and construct flow chart? What is Computer? How to construct web page and Designe it?


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

To see this, note that if there are any cycles in the Myhill graph of A then L(A) will be infinite, since any such cycle can be repeated arbitrarily many times. Conversely, if the


implementation of operator precedence grammer