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

Question 2 (10 pt): In this question we look at an extension to DFAs. A composable-reset DFA (CR-DFA) is a five-tuple, (Q,S,d,q0,F) where: – Q is the set of states, – S is the alph

implementation of operator precedence grammer

We represented SLk automata as Myhill graphs, directed graphs in which the nodes were labeled with (k-1)-factors of alphabet symbols (along with a node labeled ‘?' and one labeled

De?nition (Instantaneous Description) (for both DFAs and NFAs) An instantaneous description of A = (Q,Σ, δ, q 0 , F) , either a DFA or an NFA, is a pair h q ,w i ∈ Q×Σ*, where

De?nition Instantaneous Description of an FSA: An instantaneous description (ID) of a FSA A = (Q,Σ, T, q 0 , F) is a pair (q,w) ∈ Q×Σ* , where q the current state and w is the p

In Exercise 9 you showed that the recognition problem and universal recognition problem for SL2 are decidable. We can use the structure of Myhill graphs to show that other problems

1. An integer is said to be a “continuous factored” if it can be expresses as a product of two or more continuous integers greater than 1. Example of continuous factored integers

We have now de?ned classes of k-local languages for all k ≥ 2. Together, these classes form the Strictly Local Languages in general. De?nition (Strictly Local Languages) A langu