Use this to show that the language L = {a | i 2} is not...

  

Transcribed Image Text:

Use this to show that the language L = {a²³ | i ≥ 2} is not context-free by filling in the gaps below. (4 marks) Proof: Assume So the Pumping Lemma applies, and so for any string wEL with |w| ≥n there exist strings x, y, z, u, v such that w = xyzuv and i. yzu n ii. yu > 0 iii. xyzu'v E L for all i ≥ 0 Let So w EL and and xyzu v E L for all i 20. Now as u ≤n and so y + u ≤n. -|y|-|u| = n³ - (ly) + Let i = 0 and consider xyzuv| = |xzv| |u) n³n. Now as n ≥ 2, 4n < 3n² and so n < 3n²-3n. This means ≥ n³nn³-3n² + 3n > = (n − 1) ³. > ]xy°zu°v] > (n − 1)³, and so This is a contradiction, So n³ = and so L is not context-free. and w = xyzuv, yzu| ≤ n, │y| + |u| > 0 this means |yzu|=|y|+||+ Use this to show that the language L = {a²³ | i ≥ 2} is not context-free by filling in the gaps below. (4 marks) Proof: Assume So the Pumping Lemma applies, and so for any string wEL with |w| ≥n there exist strings x, y, z, u, v such that w = xyzuv and i. yzu n ii. yu > 0 iii. xyzu'v E L for all i ≥ 0 Let So w EL and and xyzu v E L for all i 20. Now as u ≤n and so y + u ≤n. -|y|-|u| = n³ - (ly) + Let i = 0 and consider xyzuv| = |xzv| |u) n³n. Now as n ≥ 2, 4n < 3n² and so n < 3n²-3n. This means ≥ n³nn³-3n² + 3n > = (n − 1) ³. > ]xy°zu°v] > (n − 1)³, and so This is a contradiction, So n³ = and so L is not context-free. and w = xyzuv, yzu| ≤ n, │y| + |u| > 0 this means |yzu|=|y|+||+

Answer rating: 100% (QA)

Assume L is contextfree So pumping lemma applies and so for any string w L with w n ... View the full answer