Pumping lemma for context free languages, Mathematics

Assignment Help:

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.


Related Discussions:- Pumping lemma for context free languages

Rounding, how do you round to the nearest dollars?

how do you round to the nearest dollars?

Differentiate quotient rule functions, Example of quotient rule : Let's no...

Example of quotient rule : Let's now see example on quotient rule.  In this, unlike the product rule examples, some of these functions will require the quotient rule to get the de

Explain the counting principle in maths, Explain the Counting Principle in ...

Explain the Counting Principle in maths? The fundamental counting principle is used when you want to calculate the total number of possible outcomes (or combinations) of an exp

Graphs, How do I graph a round robin pool tournment with 6 players using gr...

How do I graph a round robin pool tournment with 6 players using graph theory

Give the introduction to ratios and proportions, Give the introduction to R...

Give the introduction to Ratios and Proportions? A ratio represents a comparison between two values. A ratio of two numbers can be expressed in three ways: A ratio of "one t

Find the value of x of an arithmetic progressions, Find the value of x if 2...

Find the value of x if 2x + 1, x 2 + x +1, 3 x 2 - 3 x +3 are consecutive terms of an AP. Ans:  a 2 -a 1 =  a 3 -a 2 ⇒   x 2 + x + 1-2 x - 1 = 3x 2 - 3x + 3- x

Clique graph, Consider the clique graph below. a) How many subgraph...

Consider the clique graph below. a) How many subgraphs of G with 3 nodes are there?  b) How many of the subgraphs defined in part(a) are induced subgraphs?

Which team should get the ball at the beginning, Why is tossing a coin cons...

Why is tossing a coin considered to be a fair way of deciding which team should get the ball at the beginning of a foot ball match? Ans: equally likely because they are mutual

Integration, integral 0 to 4 integral 0 to y root of 9+ysquredxdy

integral 0 to 4 integral 0 to y root of 9+ysquredxdy

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd