Convert chomsky normal form into binary form, Theory of Computation

Assignment Help:

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.


Related Discussions:- Convert chomsky normal form into binary form

Strictly local languages, While the SL 2 languages include some surprising...

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

Transition graph for the automaton, Lemma 1 A string w ∈ Σ* is accepted by ...

Lemma 1 A string w ∈ Σ* is accepted by an LTk automaton iff w is the concatenation of the symbols labeling the edges of a path through the LTk transition graph of A from h?, ∅i to

Pumping lemma, For every regular language there is a constant n depending o...

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

Give a strictly 2-local automaton, Let L 3 = {a i bc j | i, j ≥ 0}. Give ...

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

Applying the pumping lemma, Applying the pumping lemma is not fundamentally...

Applying the pumping lemma is not fundamentally di?erent than applying (general) su?x substitution closure or the non-counting property. The pumping lemma is a little more complica

Moore machine, Construct a Moore machine to convert a binary string of radi...

Construct a Moore machine to convert a binary string of radix 4.

Computation and languages, When we study computability we are studying prob...

When we study computability we are studying problems in an abstract sense. For example, addition is the problem of, having been given two numbers, returning a third number that is

Local suffix substitution closure, The k-local Myhill graphs provide an eas...

The k-local Myhill graphs provide an easy means to generalize the suffix substitution closure property for the strictly k-local languages. Lemma (k-Local Suffix Substitution Clo

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd