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 Equivalence Problem is the question of whether two languages are equal (in the sense of being the same set of strings). An instance is a pair of ?nite speci?cations of regular

Another way of representing a strictly 2-local automaton is with a Myhill graph. These are directed graphs in which the vertices are labeled with symbols from the input alphabet of

For every regular language there is a constant n depending only on L such that, for all strings x ∈ L if |x| ≥ n then there are strings u, v and w such that 1. x = uvw, 2. |u

Let L 3 = {a i bc j | i, j ≥ 0}. Give a strictly 2-local automaton that recognizes L 3 . Use the construction of the proof to extend the automaton to one that recognizes L 3 . Gi


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

The upper string r ∈ Q+ is the sequence of states visited by the automaton as it scans the lower string w ∈ Σ*. We will refer to this string over Q as the run of A on w. The automa

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

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

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