(a) Let Li be the language of all strings of a's and b's that do not end with b and do not nite language S such that S*-L1. ntain the substring bb. Show that there is a fi Tip: List elements of L1 up to a certain length (say 3). What strings must be in S to be able to generate those strings in L? Do they seem to generate every string in Note: Once you have a candidate for S, you need to show that s*-L1, that is (1) from S you can generate only elements of L, and (2) you can generate every element of L1. For (1) argue that whatever string you generate from S will satisfy the conditions for strings in L. For (2), use induction on the length of the string in 11. Tip: if a string is in L1, Can you identify one of its symbols? Can you conclude that the rest of the string is also in Li so that you can use the induction hypothesis? f yes, you should be done, otherwise how does the string look like? While it is possible to get a description of L1 and argue that S generates it without using induction, I recommend that you do use induction, as the goal of this question s for vou to practice induction (b) Let L2 be the language of all strings of a's and b's that do not contain the substring ba Show that there is no language S such that s*-L Tip: List elements of L1 up to a certain length (say 3). What strings must be in S to be able to generate those strings in L1? Can those generate L1