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

Overview of dfa, Explain Theory of Computation ,Overview of DFA,NFA, CFG, P...

Explain Theory of Computation ,Overview of DFA,NFA, CFG, PDA, Turing Machine, Regular Language, Context Free Language, Pumping Lemma, Context Sensitive Language, Chomsky Normal For

Turing machine, Design a turing machine to compute x + y (x,y > 0) with x a...

Design a turing machine to compute x + y (x,y > 0) with x an y in unary, seperated by a # (descrition and genereal idea is needed ... no need for all TM moves)

A composable-reset DFA (CR-DFA) is a five-tuple, Question 2 (10 pt): In thi...

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

#turing machine, #can you solve a problem of palindrome using turing machin...

#can you solve a problem of palindrome using turing machine with explanation and diagrams?

Automaton theory, let G=(V,T,S,P) where V={a,b,A,B,S}, T={a,b},S the start ...

let G=(V,T,S,P) where V={a,b,A,B,S}, T={a,b},S the start symbol and P={S->Aba, A->BB, B->ab,AB->b} 1.show the derivation sentence for the string ababba 2. find a sentential form

Strictly local languages, We have now de?ned classes of k-local languages f...

We have now de?ned classes of k-local languages for all k ≥ 2. Together, these classes form the Strictly Local Languages in general. De?nition (Strictly Local Languages) A langu

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

Decision problems of regular languages, We'll close our consideration of re...

We'll close our consideration of regular languages by looking at whether (certain) problems about regular languages are algorithmically decidable.

Mapping reducibility, Can you say that B is decidable? If you somehow know...

Can you say that B is decidable? If you somehow know that A is decidable, what can you say about B?

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