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

Find regular grammar : a(a+b)*(ab*+ba*)b, Find the Regular Grammar for the ...

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

Qbasic, Ask question #Minimum 100 words accepte

Ask question #Minimum 100 words accepte

Universality problem, The Universality Problem is the dual of the emptiness...

The Universality Problem is the dual of the emptiness problem: is L(A) = Σ∗? It can be solved by minor variations of any one of the algorithms for Emptiness or (with a little le

Pendulum Swings, how many pendulum swings will it take to walk across the c...

how many pendulum swings will it take to walk across the classroom?

Project, can you plz help with some project ideas relatede to DFA or NFA or...

can you plz help with some project ideas relatede to DFA or NFA or anything

Computations of sl automata, We will specify a computation of one of these ...

We will specify a computation of one of these automata by specifying the pair of the symbols that are in the window and the remainder of the string to the right of the window at ea

Dfa to re, c program to convert dfa to re

c program to convert dfa to re

Differentiate between dfa and nfa, Differentiate between DFA and NFA. Conve...

Differentiate between DFA and NFA. Convert the following Regular Expression into DFA. (0+1)*(01*+10*)*(0+1)*. Also write a regular grammar for this DFA.

Turing machine , Let ? ={0,1} design a Turing machine that accepts L={0^m ...

Let ? ={0,1} design a Turing machine that accepts L={0^m 1^m 2^m } show using Id that a string from the language is accepted & if not rejected .

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