Let us focus on a particular z = aabaaaba and n = 7. It turns out that this is t
ID: 3792847 • Letter: L
Question
Let us focus on a particular z = aabaaaba and n = 7. It turns out that this is the wrong choice of z for n = 7, since there are some ways to break z up for which we can find the desired i, and for others, we cannot. Identify from the list below the choice of u,v,w,x,y for which there is an i that makes uviwxiy not be in L. We show the breakup of aabaaaba by placing four |'s among the a's and b's. The resulting five pieces (some of which may be empty), are the five strings. For instance, aa|b||aaaba| means u=aa, v=b, w=, x=aaaba, and y=.
a) aa|ba|a|ab|a
b) |a|abaa|a|ba
c) aa|ba|aa|ba|
d) a|a|baaab|a|
The language L = {ss | s is a string of a's and b's} is not a context-free language. In order to prove that L is not context-free we need to show that for every integer n, there is some string z in L, of length at least n, such that no matter how we break z up as z = uvwxy, subject to the constraints |vwx| n and |vx| > 0, there is some i 0 such that uviwxiy is not in L.Let us focus on a particular z = aabaaaba and n = 7. It turns out that this is the wrong choice of z for n = 7, since there are some ways to break z up for which we can find the desired i, and for others, we cannot. Identify from the list below the choice of u,v,w,x,y for which there is an i that makes uviwxiy not be in L. We show the breakup of aabaaaba by placing four |'s among the a's and b's. The resulting five pieces (some of which may be empty), are the five strings. For instance, aa|b||aaaba| means u=aa, v=b, w=, x=aaaba, and y=.
a) aa|ba|a|ab|a
b) |a|abaa|a|ba
c) aa|ba|aa|ba|
d) a|a|baaab|a|
Explanation / Answer
Correct answer is : c) aa|ba|aa|ba|
Explanation:
If the result of pump out(q==0) to get aababa.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.