Convert chomsky normal form into binary form, Theory of Computation

Suppose G = (N, Σ, P, S) is a reduced grammar (we can certainly reduce G if we haven't already). Our algorithm is as follows:

1. Define maxrhs(G) to be the maximum length of the right hand side of  any  production.

2. While maxrhs 3 we convert G to an equivalent reduced grammar G' with smaller maxrhs.

3. a) Choose a production A → α where is of maximal length in G.

b) Rewrite α as α1α2 where |α1| = |α1|/2 (largest integer ≤ |α1|/2) and  |α2| = |α2|/2 (smallest integer ≥ |α2|/2)

c) Replace A -> α in P by A  -> α1B and B -> α2

If we repeat step 3 for all productions of maximal length we create a grammar G' all of whose productions are of smaller length than maxrhs.

We can then apply the algorithm to G' and continue until we reach a grammar that has maxrhs ≤ 2.

Posted Date: 3/9/2013 1:52:37 AM | Location : United States







Related Discussions:- Convert chomsky normal form into binary form, Assignment Help, Ask Question on Convert chomsky normal form into binary form, Get Answer, Expert's Help, Convert chomsky normal form into binary form Discussions

Write discussion on Convert chomsky normal form into binary form
Your posts are moderated
Related Questions
The fact that regular languages are closed under Boolean operations simpli?es the process of establishing regularity of languages; in essence we can augment the regular operations

The initial ID of the automaton given in Figure 3, running on input ‘aabbba' is (A, aabbba) The ID after the ?rst three transitions of the computation is (F, bba) The p

As we are primarily concerned with questions of what is and what is not computable relative to some particular model of computation, we will usually base our explorations of langua

What is the purpose of GDTR?

distinguish between histogram and historigram

And what this money. Invovle who it involves and the fact of,how we got itself identified candidate and not withstanding time date location. That shouts me media And answers who''v

The path function δ : Q × Σ*→ P(Q) is the extension of δ to strings: Again, this just says that to ?nd the set of states reachable by a path labeled w from a state q in an

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

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

write grammer to produce all mathematical expressions in c.