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

implementation of operator precedence grammer

The SL 2 languages are speci?ed with a set of 2-factors in Σ 2 (plus some factors in {?}Σ and some factors in Σ{?} distinguishing symbols that may occur at the beginning and en

Application of the general suffix substitution closure theorem is slightly more complicated than application of the specific k-local versions. In the specific versions, all we had

what are the advantages and disadvantages of wearable computers?

S-->AAA|B A-->aA|B B-->epsilon

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

shell script to print table in given range

Find the Regular Grammar for the following Regular Expression:                    a(a+b)*(ab*+ba*)b.

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