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
Another way of interpreting a strictly local automaton is as a generator: a mechanism for building strings which is restricted to building all and only the automaton as an inexh

implementation of operator precedence grammer

We can then specify any language in the class of languages by specifying a particular automaton in the class of automata. We do that by specifying values for the parameters of the

The Equivalence Problem is the question of whether two languages are equal (in the sense of being the same set of strings). An instance is a pair of ?nite speci?cations of regular

Prove that Language is non regular TRailing count={aa ba aaaa abaa baaa bbaa aaaaaa aabaaa abaaaa..... 1) Pumping Lemma 2)Myhill nerode

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

Given any NFA A, we will construct a regular expression denoting L(A) by means of an expression graph, a generalization of NFA transition graphs in which the edges are labeled with

Let there L1 and L2 . We show that L1 ∩ L2 is CFG . Let M1 be a decider for L1 and M2 be a decider for L2 . Consider a 2-tape TM M: "On input x: 1. copy x on the second

Computation of a DFA or NFA without ε-transitions An ID (q 1 ,w 1 ) computes (qn,wn) in A = (Q,Σ, T, q 0 , F) (in zero or more steps) if there is a sequence of IDs (q 1

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