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
Find the Regular Grammar for the following Regular Expression: a(a+b)*(ab*+ba*)b.


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

Sketch an algorithm for the universal recognition problem for SL 2 . This takes an automaton and a string and returns TRUE if the string is accepted by the automaton, FALSE otherwi

The key thing about the Suffx Substitution Closure property is that it does not make any explicit reference to the automaton that recognizes the language. While the argument tha

A common approach in solving problems is to transform them to different problems, solve the new ones, and derive the solutions for the original problems from those for the new ones

We got the class LT by taking the class SL and closing it under Boolean operations. We have observed that LT ⊆ Recog, so certainly any Boolean combination of LT languages will also

Both L 1 and L 2 are SL 2 . (You should verify this by thinking about what the automata look like.) We claim that L 1 ∪ L 2 ∈ SL 2 . To see this, suppose, by way of con

what are composition and its function of gastric juice

S-->AAA|B A-->aA|B B-->epsilon