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

Matrices, Ask qudefination of empty matrixestion #Minimum 100 words accepte...

Ask qudefination of empty matrixestion #Minimum 100 words accepted#

What is the median of her scores, Jody's English quiz scores are 56, 93, 72...

Jody's English quiz scores are 56, 93, 72, 89, and 87. What is the median of her scores? To find out the median, first put the numbers in sequence from least to greatest. 56, 7

Find out the surface area of the solid - parametric curve, Find out the sur...

Find out the surface area of the solid acquired by rotating the following parametric curve about the x-axis. x = cos 3 θ y = sin 3 θ  0 ≤ θ ≤ ?/2 Solution We wil

Differential equations, Verify Liouville''''s formula for y "-y" - y'''' + ...

Verify Liouville''''s formula for y "-y" - y'''' + y = 0 in (0, 1) ?

Subtraction involving negative numbers, Q. Subtraction Involving Negative N...

Q. Subtraction Involving Negative Numbers? In order to subtract positive and negative numbers, you need to be aware of the Rule for Subtraction. This rule states that subtracti

Matrix, how to find eigen value for the given matrix 122 021 -122

how to find eigen value for the given matrix 122 021 -122

Find the 20th term of arithmetic progressions, Find the 20 th term from th...

Find the 20 th term from the end of the AP 3, 8, 13........253. Ans:    3, 8, 13 .............. 253 Last term = 253 a20 from end = l - (n-1)d 253 - ( 20-1) 5 253

Value of perfect information, Value of perfect information This relates...

Value of perfect information This relates to the amount that we would pay for an item of information such would enable us to forecast the exact conditions of the market and act

Multiplication of two like terms with opposite signs, The product of -7ab a...

The product of -7ab and +3ab is (-7 x 3) a 2  b 2  = -21a 2  b 2 . In other words, a term with minus sign when multiplied with a term having a positive sign, gives a product having

Find the value a2 + ß2 and (a - ß)2, If  α,β are the zeros of the polynom...

If  α,β are the zeros of the polynomial 2x 2 - 4x + 5 find the value of a) α 2 + β 2   b) (α - β) 2 . Ans : p (x) = 2 x 2 - 4 x + 5           (Ans: a) -1 , b) -6) α + β =

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