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
Question 2 (10 pt): In this question we look at an extension to DFAs. A composable-reset DFA (CR-DFA) is a five-tuple, (Q,S,d,q0,F) where: – Q is the set of states, – S is the alph

#Your company has 25 licenses for a computer program, but you discover that it has been copied onto 80 computers. You informed your supervisor, but he/she is not willing to take an

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

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.

We developed the idea of FSA by generalizing LTk transition graphs. Not surprisingly, then, every LTk transition graph is also the transition graph of a FSA (in fact a DFA)-the one

draw pda for l={an,bm,an/m,n>=0} n is in superscript

How useful is production function in production planning?

Can v find the given number is palindrome or not using turing machine

Strictly 2-local automata are based on lookup tables that are sets of 2-factors, the pairs of adjacent symbols which are permitted to occur in a word. To generalize, we extend the