Question: 2. 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

2. 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-= nwn, subject to the constraints |vwx_ n and lvxl> 0, there is some i 20 such that n'wry 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 inwy not be in L. We show the breakup of aabaaaba by placing four I's among the a's and b's. The resulting five pieces (some of which may be empty), are the five strings. For instance, aalblaaabal means u=aa, v=b, w=, x=aaaba, and E. C) a) alab aaalba O b) aalba alabla O c) aalba aaba o d) alaba alaba
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
