Context free grammar, Theory of Computation

A context free grammar G = (N, Σ, P, S)  is in binary form if for all productions

A we have |α| ≤ 2. In addition we say that G is in Chomsky Normaml Form (CNF) if it is in binary form and if the only sorts of production have the form

            A → a             (where a is a terminal symbol)

or

            A → BC          (where B and C are non-terminals)

We will show that every CFG G is λ- equivalent to a grammar G' that is in CNF (i.e. the only difference between G and G' is that may or may not be included. Since we know how to test for the presence of in our languages we will be able to construct equivalent grammars.

Posted Date: 3/9/2013 1:45:35 AM | Location : United States







Related Discussions:- Context free grammar, Assignment Help, Ask Question on Context free grammar, Get Answer, Expert's Help, Context free grammar Discussions

Write discussion on Context free grammar
Your posts are moderated
Related Questions
We developed the idea of FSA by generalizing LTk transition graphs. Not surprisingly, then, every LTk transition graph is also the transition graph of a FSA (in fact a DFA)-the one

We now add an additional degree of non-determinism and allow transitions that can be taken independent of the input-ε-transitions. Here whenever the automaton is in state 1

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

Describe the architecture of interface agency

The fundamental idea of strictly local languages is that they are speci?ed solely in terms of the blocks of consecutive symbols that occur in a word. We'll start by considering lan

Exercise:  Give a construction that converts a strictly 2-local automaton for a language L into one that recognizes the language L r . Justify the correctness of your construction.

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

Automata and Compiler (1) [25 marks] Let N be the last two digits of your student number. Design a finite automaton that accepts the language of strings that end with the last f

If the first three words are the boys down,what are the last three words??

What are the benefits of using work breakdown structure, Project Management