2. The language L = {ss | s is a string of a\'s and b\'s} is not a context-free

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 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

Explanation / Answer

Hi,
In the given options we have to choose the combination such that the string formed is not of the form SS
lets look at each of thr options
1. a|ab|aaa|b|a
in this string is always of the form a (ab) aaa (b) a, if we choose i=2, the string is not in L, we get
a (ab)(ab)a aa(b)(b) a - which is of odd length, and hence this is the answer
2.aa|ba|a|ab|a
in this string is always of the form aa (ba) a (ab) a, due to the middle a and the inverted groups of ba and ab, this will always be of form SS, hence not true
3.aa|ba|aa|ba|
even in this, the string is always in form aa (ba) aa (ba) which is in form SS, hence not true
4. a|aba|a|aba|
as we can see this, for any number of repetiion of aba, the string will always be of form a (aba) a (aba), which is of form SS, hence not true

Thumbs up if this was helpful, otherwise let me know in comments

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.