Reference no: EM132500472

APM 3430 Theory of Computation - Oakland University

Question 1.
(a) Let L1 be the language of all strings of a's and b's that do not end with b and do not contain the substring bb. Show that there is a finite language S such that S∗ = L1.

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? Do they seem to generate every string in L1?

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 L1, 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 L1. For (2), use induction on the length of the string in L1. 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 L1 so that you can use the induction hypothesis? If 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 is for you to practice induction.

(b) Let L2 be the language of all strings of a's and b's that do not contain the substring bb. Show that there is no language S such that S∗ = L2.

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? Will those have to generate strings not in L1?

Question 2. For each n ≥ 0 define the strings an and bn in {0, 1}∗ as follows: a0 = 0, b0 = 1, and for n > 0, an = an-1bn-1 and bn = bn-1an-1 (the operation here is concatenation, not multiplication, hence, e.g., a1 = 01 and b1 = 10). Use induction on n to show that the strings a2n and b2n are palindromes for every n ≥ 0.

Tip: Write down the first few strings to get a feel of how they look like. In your induction step try to write a2(n+1) and b2(n+1) in terms of a2n and b2n using the given recursion, and use the induction hypothesis that they are palindromes, so aR = a2n and bR = b2n.

Question 3. Let L1 ⊂ {a, b}∗ be the language defined recursively as follows:
(a) Λ ∈ L1.
(b) For every x ∈ {a, b}∗, if x is in L1, then ax, xb, and xba are also in L1.
(c) Only those strings are in L1 that can be obtained by applying (a) and (b) finitely many times.
Let L2 ⊂ {a, b}∗ be the language containing every string in {a, b}∗ that doesn't contain
baa as a substring. Show that L1 = L2.

Question 4. Find a recursive definition for the language L = aibj i, j N, i j 3i (like the one in problem 3), and show that your definition is correct.

Tip: Your recursive definition should be similar to the one in Problem 3. You want to make sure that (1) all the a's are before all the b's, and (2) the number of b's in the string is not too small and not too large. So, whenever you add an a, how many b's should you add?
Once you have a recursive definition, you may want to give a new name for the language generated by it to avoid confusion. Then you want to show that (1) you can generate only elements of L, and (2) you can generate every element of L. For (1) you want to argue (maybe using structural induction) that every string you generate will have the form strings in L satisfy. For (2) you want to show that every string in L can be generated. I suggest using induction on i in the defintion of L.

Question 5. Draw an FA that accepts the language L7, the set of strings in 0, 1 ∗ that are binary representations of natural numbers divisible by 7 (leading zero is not allowed except for 0 itself, so for example, 10101 L7, 0 L7, but 0111 L7). Justify that your FA accepts L7.

Tip: Use the states to remember the remainder of the number one has read so far modulo 7 as we did in class. Remember that leading 0's are not allowed except the number 0 itself (but 00 should not be accepted), so you have to deal with that separately. Figure out how the remainder changes when a 0 or a 1 is appended to the string.

Note: There is no need to give a formal definition of the FA, a picture suffices. As your justification, explain briefly the idea behind the FA, and how you got the new remainders (best to include the table with the new remainders).

Attachment:- Theory of Computation.rar