Pumping lemma for context free languages, Mathematics

1. Construct a grammar G such that L(G) = L(M) where M is the PDA in the previous question. Then show that the word aaaabb is generated by G.

2. Prove, using the Pumping Lemma for Context-Free Languages, that the language L = {ak | k is a perfect square} is not context-free.

2. Consider the language L = {ak bk | k > 0}. Explain whether this language is context-free, context-sensitive, recursive, recursively, enumerable, and/or regular. While formal proofs are not required, justify your assertions.

Posted Date: 3/26/2013 7:55:54 AM | Location : United States







Related Discussions:- Pumping lemma for context free languages, Assignment Help, Ask Question on Pumping lemma for context free languages, Get Answer, Expert's Help, Pumping lemma for context free languages Discussions

Write discussion on Pumping lemma for context free languages
Your posts are moderated
Related Questions
Describe the Sample of Exponents ? Imagine, for example, that you are the P.E. coach at your school, and you need to divide one of your classes into teams. Your team has 45 stu

what shapes can go into a triangular prism

Infinite Limits : In this section we will see limits whose value is infinity or minus infinity.  The primary thing we have to probably do here is to define just what we mean w

Graph y = cos (x) Solution: There actually isn't a whole lot to this one.  Given the graph for -4 ? ≤ x ≤ 4 ? . Note that we can put all values of x in cosine (that wo

how can you memorise you times facts

On dividing the polynomial 4x 4 - 5x 3 - 39x 2 - 46x - 2 by the polynomial g(x) the quotient is x 2 - 3x - 5 and the remainder is -5x + 8.Find the polynomial g(x). (Ans:4 x 2 +

Consider the system of linear equations X + ay = 1 2x + 8y = b Where a and b are real numbers. (a)  Write out the augmented matrix for this system of linear equations.

Let us now look at some activities that can be organised with preschoolers to develop their ability to classify. 1. You could start by giving children different materials to pla

A rectangular container is 15 cm wide and 5 cm long, and contains water to a depth of 8 cm. An object is placed in the water and the water rises 2.3 cm. Determine the volume of the

Comparison - the difference between two groups or numbers, namely, how much one is greater than the other, how much more is in one group than in the other. (e.g., if Munna has