Theory of Computation HW4 Solutions (151 points total)
Below is a list of the assigned questions, with the total number of points allocated for each question in parentheses (a 0 indicates that the question will not be graded).
Ch 1.4 questions: 1.29bc(15), 1.30 (15), 1.46ac (30), 1.55abcefgij (28) Ch 2.1 questions: 2.1 (12), 2.3 (0), 2.4 (21), 2.6ac (5), 2.9 (10), 2.14 (15)
Chapter 1.4 Questions: 1.29
Copyright By PowCoder代写 加微信 powcoder
b) (15 points) Use the pumping lemma to show that A2 = {www| w {a,b}*} is not regular
Assume that A2 = {www| w {a,b}*} is regular. Let p be the pumping length given by the pumping lemma. Choose s to be the string apbapbapb. Because s is a member of A2 and s is longer than p, the pumping lemma guarantees that s can be split into three pieces s = xyz, where for any i ≥ 0 the string xyiz is in A2 (condition 1), |y| > 0 (condition 2) and |xy| ≤ p (condition 3).
Condition 3 implies that y must contain only a’s (and thus z contains bapbapb). Now if we pump y once to get xyyz, then the start of the string will have at least p+1 a’s, and hence the resulting string A2. Note that this proof is effectively identical in spirit to the proof that ww is not regular.
c) (not graded) Use the pumping lemma to show that A3 = {a2n| n ≥ 0}, where a2n means a string of 2n a’s.
Assume that A3 = {a2n| n ≥ 0} is regular. Let p be the pumping length given by the pumping lemma.
Choose s to be the string a2p. Because s is a member of A3 and s is longer than p, the pumping lemma guarantees that s can be split into three pieces s = xyz, where for any i ≥ 0 the string xyiz is in A2 (condition 1), |y| > 0 (condition 2) and |xy| ≤ p (condition 3).
The third condition states that |xy| ≤ p. Furthermore, p < 2p and so |y| < 2p (|y| ≤ p but we are okay with using just the 2p and that is sufficient in this case). Therefore |xyyz| = |xyz| + |y| < 2p + 2p = 2p+1 and hence |xyyz| < 2p+1. The second condition requires that |y| > 0, so since |xyz| = 2p, |xyyz| must be at least one bigger and hence we can bound it below and thus we get 2p < |xyyz| < 2p+1. Thus the length of xyyz cannot be a power of 2, since it must be between successive powers of 2. Therefore xyyz A3, a contradiction. Therefore A3 is not regular.
1.30 (15 points) We need to find the error in the “proof” that 0*1* is not regular (since we know it is regular). Here is the proof:
The proof is by contradiction. Assume that 0*1* is regular. Let p be the pumping length for 0*1* given by the pumping lemma. Choose s = 0p1p. You know that s is a member of 0*1*, but Example 1.73 shows that it cannot be pumped. Thus you have a contradiction. So 0*1* is not regular.
The error is that 0p1p can be pumped, even though it could not be pumped in Example 1.73. Here is how it can be pumped. Let x = 0, y = 0 and z = 0p-21p. The conditions are satisfied because:
i) for any i ≥ 0, xyiz = 00i0p-21p which is in 0*1*
ii) |y| = 1 > 0, and
iii) |xy| = 2 ≤ p.
So what might have been the confusion? First, when picking the string to pump, you should pick the 1
hardest possible string. Remember this is a proof by contradiction and you need to be able to pump all string, so it makes sense to pick a hard one. However, when you pump the string, the resulting string must be in the original language, but need not adhere to the pattern represented by the string you picked. In Example 1.73, the language is 0n1n, but here it is only 0*1*. In example 1.73, the pumped string had to be in 0n1n whereas here it only needed to be in 0*1*. You may have been fooled because the string to pump was 0p1p and you may therefore have jumped to the conclusion that the pumped string had to be in 0n1n. Note that in this case if we pump to get xyyz, we would have the string 0P+11P, which clearly belongs to the language 0*1*.
1.46 (30 points) Prove that the following languages are not regular. You may use the pumping lemma and closure of regular languages under union, intersection, and complement. (15 points each part)
a) {0n1m0n|m,n ≥ 0}
Assume L = {0n1m0n|m,n ≥ 0} is regular. Let p be the pumping length given by the pumping lemma. The string s = 0p10p L, and |s| ≥ p. The pumping lemma implies that s can be written as xyz. By condition 3, y can contain only 0’s. Thus we have x = 0a, y = 0b, and z = 0c10p, where b ≥ 1 and a + b + c = p. However, the string s’ = xy0z = 0a+c10p L, since a+c < p. That contradicts the pumping lemma. Note that while here we pumped down, if we pumped up then we would also have a problem, since then we would have more than p 0’s at the start.
c) {w| w {0,1}* is not a palindrome}
Assume C = {w| w {0,1}* is a palindrome} is regular. Let p be the pumping length given by the pumping lemma. The string s = 0p10p C and |s| ≥ p. Now we can follow the exact same argument as in part a. Basically, if we pump then the number of 0’s at the start won’t equal the number at the end, leading to a contradiction. So, we can conclude that C is not a regular language. Since regular languages are closed under complement, since C is not regular, neither is the complement of C, which is the language we were originally asked about.
1.55 (28 points: 4 points each graded part) Find the minimum pumping lengths for all of the following languages:
a. 0001* (not graded)
The minimum pumping length is 4. The string 000 is in the language but cannot be pumped, so 3 is not a pumping length. If s has length 4 or more it has 1’s. By dividing s into xyz, where x is 000 and y is the first 1 and z is everything afterward, we satisfy the 3 conditions of the pumping lemma.
The minimum pumping length is 1. The pumping length cannot be 0 because the string ε is in the language and it cannot be pumped. Every non-empty string in the language can be divided into xyz, where x = ε, y is the first character, and z is the remainder.
Let me go over the part about not being able to have a pumping length of 0 if ε is in the language, since we will use this several times. You can never pump the string ε with pumping length equal to 0, since |y| > 0 by condition 2. However, if ε is not in the language, then even if pumping length is 0, the string s must be in the language (see the definition of the pumping lemma), so even with a pumping length of 0, the value of p will be more than 0. So, if ε is not in the language, you may be able to pump with a pumping length of 0 (because p will be > 0).
c. 001 0*1*
The language is the same as in part b, so the pumping length is again 1.
d. 0*1+0+1* 10*1 (not assigned so not graded)
The minimum pumping length is 3. The pumped length cannot be 2 since the string 11 is in the language and cannot be pumped. Let s be a string in the language of length at least 3. If s is generated by 0*1+0+1*, we can write it as xyz where x is the empty string, y is the first symbol of s, and z is the remainder of s. Breaking up s this way shows that it can be pumped. If s is generated by 10*1, we can write is at xyz where x=1, y=0, and z is the remainder of s. Here is another division that I came up with. For the 0*1+0+1* part of the language, let x = any leading 0s followed by one 1. Then let y = 1 if there is more than one 1 in the middle; else y=0. The let z be the remainder. So, you can pump either way using y, for either y=0 or y=1, since the resulting string would still be in the language.
The minimum pumping length is 1. The pumping length cannot be 0, as in part b, since the empty string is in the language and cannot be pumped. Any string of length 2 or more contains 01 and hence can be pumped by dividing it into x = ε, y = 01, and z is the rest. But since there is no string of length 1 in the language, 1 also works, and hence is the correct answer. (Assign 3 points out of 4 if the answer given is 2 rather than 1.)
The minimum pumping length is 1. The pumping length cannot be 0 because the empty string is in the language and cannot be pumped. The language has no strings of length 1 or more so 1 is a pumping length, trivially.
g. 1*01*01*
The minimum pumping length is 3. The string 00 is in the language and cannot be pumped. Every string in the language of length 3 has at least one 1 within the first 3 symbols so it can be pumped by letting y be that 1 and letting x be the symbols to the left of y and z be the symbols to the right of y.
The minimum pumping length is 5. The string 1011 really can never be pumped. By setting the pumping length to 5, there is no string of length 5 that is in the language, so the pumping lemma holds, as the book likes to say, “vacuously”.
The minimum pumping length is 1. It cannot be 0 since ε is in the language. However, if the length is 1 or more, just assign the string s to y and then pumping it will always yield something in the language.
Chapter 2.1 Questions:
2.1 (12 points) Here are the derivations: a) E→T→F→a
b) E→E+T→T+T→F+T→F+F→a+F→a+a
c) E → E+T → E+T+T → T+T+T → F+T+T → F+F+T →F+F+F → a+F+F →a+a+F → a+a+a d) E→T→F→(E)→(T)→(F)→((E))→((T))→((F))→((a))
(1.5 points for the derivation and 1.5 points for the parse tree for each part)
The parse trees for a and d are essentially linear and hence not much different than the derivations. 2.3 (0 points: not graded) The solution to 2.3 is in the textbook.
The one thing that may not be obvious is that the * means that the derivation can take 0, 1, or many steps; if the * is not there it can only take one step.
2.4 (21 points: Only parts b, c and e graded, for 7 points each). Give CFGs that generate the following languages. In all parts the alphabet is {0,1}. Other solutions are possible and should receive full credit.
a) {w| w contains at least three 1s} Solution in book S → R1R1R1R
R → 0R|1R|ε
b) {w| w starts and ends with the same symbol} S → 0R0 | 1R1 | ε
R →0R | 1R | ε
Do not take off points if a solution is generated which does not allow the empty string. The empty
string does start and end with the same character (vacuously!).
c) {w| the length of w is odd}
S →0 | 1 | 00S | 01S | 10S | 11S
d) {w| the length of w is odd and its middle symbol is a 0} S → 0 | 0S0 | 0S1 | 1S0 | 1S1
e) {w| w = wR, that is, w is a palindrome} S →0S0 | 1S1 | 0 | 1 | ε
f) The empty set (not graded)
Solution in book
2.6) (5 points) Give CFGs generating the following languages
(since both solutions are in the book, give full credit as long as the student writes something reasonable to indicate they tried—even if they do not copy the solution and get it wrong)
a) The set of strings over the alphabet {a,b} with more a’s than b’s Solution in book S → TaT
T → TT | aTb | bTa | a | ε
c) {w#x|wRisasubstringofxforw,x{0,1}*} Solutioninbook
This one is very difficult. I would not expect you to come up with this by yourself. However, I would expect that, if given this solution, you can understand it. The basic idea is as follows. For the most part, the T variable generates palindromes. This guarantees that the reverse of the left half is equal to the right half. But it only needs to be a substring, so we can then append arbitrary 0’s and 1’s before and after the right half. The X variable permits the arbitrary strings. The T → #X takes care of the arbitrary strings at the start of the string after the # and the X in S → TX takes care of it at the end. An example is shown after the grammar.
T → 0T0 | 1T1 | #X X → 0X | 1X | ε
Here is an example derivation: S → TX → 0T0X → 01T10X → 01#X10X … Note that at this point we have the reverse of “01” in the string after the # and the X’s can be expanded to anything.
2.9) (10 points) Give a CFG that generates the language A = {aibjck| i=j or j=k, where i, j, k ≥ 0}
Note that the or in the description is a hint that we can solve both parts separately and then combine the solutions by unioning the two CFGs. Do not take off points if the student only lists the rules.
G = (V, , R, S), V = (S, Eab, Ebc, C, A), and ={a,b,c}.
The rules are:
S → EabC | A → a Eabb | ε Ebc →bEbcc|ε C → Cc | ε
A → Aa | ε
Initially substituting EabC for S yields strings with an equal number of a’s and b’s followed by any number of c’s. Initially substituting Ebc for S generates any string with an equal number of b’s and c’s prepended by any number of a’s.
The grammar is ambiguous. Consider the fact that ε can be generated by using either of the two substitutions for S. (Do not take off any points if the student does not get this part right or forgets to include it)
2.14) (15 points) Convert the following CFG into an equivalent CFG in Chomsky Normal form, using the procedure given in Theorem 2.9:
A → BAB | B | ε B → 00 | ε
Step 1: Add a new start variable S0 → A
A → BAB | B | ε
B → 00 | ε
Step 2: Remove ε rules 2a) remove A → ε
S0 → A | ε
A → BAB | B | BB
B → 00 | ε
2b) remove B → ε
S0 → A | ε
A → BAB | B | BB | AB | BA | A B → 00
Step 3: Remove Unit rules
3a) removeAin S0 →A
S0→ BAB | B | BB | AB | BA | ε A → BAB | B | BB | AB | BA
3b) remove S0→ B and A → B S0→ BAB | 00 | BB | AB | BA | ε A → BAB | 00 | BB | AB | BA
(A → A does not do anything)
4a) Shorten rules with 3 or more tokens on right side Introduce D → AB
S0→ BD | 00 | BB | AB | BA | ε A → BD | 00 | BB | AB | BA
4b) If there are two tokens and they include terminal symbols, add a rule with new variable going to the terminal
Here add C → 0 and substitute in to get final answer
S0→ BD | CC | BB | AB | BA | ε A → BD | CC | BB | AB | BA
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com