Binary form and chomsky normal form, Theory of Computation

Normal forms are important because they give us a 'standard' way of rewriting and allow us to compare two apparently different grammars G1  and G2. The two grammars can be shown to be equal provided they have the same normal form.

Additionally by rewriting grammars in a standard way we have a structure that can form the input to future stages of a process. For example programs in a high level programming languages have to be converted in more 'basic' instructions via a parser  and it is helpful if the inputs to such a process are of a uniform type.

In this section we introduce one of the standard normal forms commonly used; this is known as Chomsky Normal Form.

Posted Date: 3/9/2013 1:43:15 AM | Location : United States







Related Discussions:- Binary form and chomsky normal form, Assignment Help, Ask Question on Binary form and chomsky normal form, Get Answer, Expert's Help, Binary form and chomsky normal form Discussions

Write discussion on Binary form and chomsky normal form
Your posts are moderated
Related Questions

Since the signi?cance of the states represented by the nodes of these transition graphs is arbitrary, we will allow ourselves to use any ?nite set (such as {A,B,C,D,E, F,G,H} or ev

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


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.

Another striking aspect of LTk transition graphs is that they are generally extremely ine?cient. All we really care about is whether a path through the graph leads to an accepting

turing machine for prime numbers

what exactly is this and how is it implemented and how to prove its correctness, completeness...

1. Simulate a TM with infinite tape on both ends using a two-track TM with finite storage 2. Prove the following language is non-Turing recognizable using the diagnolization

Theorem The class of ?nite languages is a proper subclass of SL. Note that the class of ?nite languages is closed under union and concatenation but SL is not closed under either. N