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
proof ogdens lemma .with example i am not able to undestand the meaning of distinguished position .

When we say "solved algorithmically" we are not asking about a speci?c programming language, in fact one of the theorems in computability is that essentially all reasonable program

Construct a PDA that accepts { x#y | x, y in {a, b}* such that x ? y and xi = yi for some i, 1 = i = min(|x|, |y|) }. For your PDA to work correctly it will need to be non-determin

Exercise:  Give a construction that converts a strictly 2-local automaton for a language L into one that recognizes the language L r . Justify the correctness of your construction.

Ask question #Minimum 100 words accepte

When an FSA is deterministic the set of triples encoding its edges represents a relation that is functional in its ?rst and third components: for every q and σ there is exactly one

The fundamental idea of strictly local languages is that they are speci?ed solely in terms of the blocks of consecutive symbols that occur in a word. We'll start by considering lan

write grammer to produce all mathematical expressions in c.


While the SL 2 languages include some surprisingly complex languages, the strictly 2-local automata are, nevertheless, quite limited. In a strong sense, they are almost memoryless