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
what exactly is this and how is it implemented and how to prove its correctness, completeness...

write grammer to produce all mathematical expressions in c.

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

A common approach in solving problems is to transform them to different problems, solve the new ones, and derive the solutions for the original problems from those for the new ones

All that distinguishes the de?nition of the class of Regular languages from that of the class of Star-Free languages is that the former is closed under Kleene closure while the lat


We represented SLk automata as Myhill graphs, directed graphs in which the nodes were labeled with (k-1)-factors of alphabet symbols (along with a node labeled ‘?' and one labeled

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

Given any NFA A, we will construct a regular expression denoting L(A) by means of an expression graph, a generalization of NFA transition graphs in which the edges are labeled with

A Turing machine is a theoretical computing machine made-up by Alan Turing (1937) to serve as an idealized model for mathematical calculation. A Turing machine having of a line of