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
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 .

One might assume that non-closure under concatenation would imply non closure under both Kleene- and positive closure, since the concatenation of a language with itself is included


The Last Stop Boutique is having a five-day sale. Each day, starting on Monday, the price will drop 10% of the previous day’s price. For example, if the original price of a product

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

A problem is said to be unsolvable if no algorithm can solve it. The problem is said to be undecidable if it is a decision problem and no algorithm can decide it. It should be note

Suppose A = (Σ, T) is an SL 2 automaton. Sketch an algorithm for recognizing L(A) by, in essence, implementing the automaton. Your algorithm should work with the particular automa

The path function δ : Q × Σ*→ P(Q) is the extension of δ to strings: Again, this just says that to ?nd the set of states reachable by a path labeled w from a state q in an


The project 2 involves completing and modifying the C++ program that evaluates statements of an expression language contained in the Expression Interpreter that interprets fully pa