Dr. Weiss, CISC 4090/5200 Quiz 2 SOLUTIONS
Name: __________________________________________
Each T/F question counts for 12 points (circle the answer) and question 3 counts for 28 points. You have 10 minutes to complete the quiz.
1. If an NFA with n states is converted to a DFA, the DFA will have n2 states. T F
Copyright By PowCoder代写 加微信 powcoder
2. The language L = {001} is regular (this language has one element) T F
3. Let L = {ww| w {0,1}*}, which is exactly the language of Example 3 that we used in the pumping lemma section (L is the language of binary strings where the first half equals the second half). We proved that this language is not regular, but if you use the string s = 0P0P, you are unable to prove it is not regular (it is a bad string to choose). Show why this is true by providing a valid partition of s below (fill in each blank) that demonstrates that this string can be pumped.
s = 0P0P = xyz, where: x = _____________
y = _____________
z = ______________
The key here is that y must contain an even number of 0’s, so that when you pump on it, the number remains even. Only an even number of 0’s would remain of the form ww since the first half must equal the second half. The second thing is that xyz together must equal the original string s, which has 2P 0’s. If you do not have this, you do not even have a valid partition. To have a valid partition that obeys the pumping lemma conditions, note that |xy| <= p. My solution above has all that is needed, an even number of 0’s for y, |xy| <=p (at least for some p) and together xyz has 2P 0’s.
4. A context free grammar can generate all strings of the form: 0n1n T F
5. The pumping lemma can be used to prove a language regular or not regular T F
6. Assuming Σ = {0,1}, then Σ*111Σ* represents the language of binary strings with at T F least 3 1’s.
7. The pumping lemma involves showing that for one string you cannot find any T F partition of that string (that adheres to the three conditions) that can be
pumped. The focus of this question is the two underlined words- the rest of
the sentence is not at issue.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com