Theory of Computation, Dr. 2022 Midterm Solutions (100 Points)
Name: _______________________________________
Directions:
Answer the questions as well as you can. Partial credit will be given, so show your work where appropriate. Try to be precise in your answers in order to maximize your points. You have 75 minutes to complete the exam. I do provide the recommended time range for each question. Even if you take the maximum recommended time on every question you will finish. Good luck.
Copyright By PowCoder代写 加微信 powcoder
Page 1 of 7
Questions Points Topic Recommend Score Time (min)
1 9 NFA 2-5 1 9 DFA 3-8
12 NFA 5-10 Regular Expr.
26 T/F 13-20
18 CFG 8-15
15 Pumping 3-7 Lemma
12 NFA, DFA 5-10 4 Extra Credit —
Note: I provide the full pumping lemma for you on Question 6, the only full pumping lemma proof on the exam. If you think it helpful you can refer to it for any short pumping lemma related questions.
1. (9 points) Provide the formal definition for the NFA N shown to the right. Hint: 5-tuple. Recommended time: 2-5 minutes.
N = {Q, , , q0, F}
Q = {q1, q2, q3}
= {a, b}
q0 = q1 (or just put q1 instead of q0 above) F = {q1}
State a b ɛ
q1 { q2} { q3} q2 { q2, q3} { q3} q3 {q1}
Page 2 of 7
2. (9 points) Draw the DFA that accepts all binary strings that begin with 2 0’s and end with a 1. Recommended time: 3-8 minutes.
3. (12 points) NFA & Regular Expression Question. Recommended time: 5-10 minutes.
(a) (9 points) Draw an NFA N below that accepts all binary strings where the 3rd to last symbol is a “0” or the last symbol is a “1”. For full credit you must use “NFA
thinking” and should not have edges that are not needed.
(b) (3 points) In the blank near the bottom of the page put the equivalent regular expression (i.e., the regular expression that represents the language of N). You can assume = {0,1}. For full credit your NFA must have the minimum number of states and transitions.
Please note that the question relates to the union of two sub-languages. The first solution is what I believe is the most obvious and received full credit. You stay in the start state until you nondeterministically guess there is a 0 coming up in the third to last position or a 1 in the last position. The second solution simply merges the two accept states, as a minor optimization.
Page 3 of 7
(b) Equivalent regular expression: *0 *1__________________
4. True/False & Multiple Choice (26 points: 13 questions, 2 points each) _________ Recommended Time: 13 – 20 minutes
a. Regular languages are closed under the union, concatenation, Kleene Closure (*), and complement operations.
b. A DFA can never accept the empty string
c. The language (01)n is regular.
d. The language 0n1m, n>m is regular.
e. If Σ = {0,1} every state in a DFA must have exactly 2 outgoing edges.
f. The language 0n1n is regular.
g. The language 0n1n is context free.
h. If an NFA has n states, then the process to convert it to a DFA generally requires n2 states since you must remember pairs of states.
i. Any regular expression can be converted into an NFA.
j. A CFG is ambiguous if it has more than one leftmost derivation or more than one parse tree.
k. The minimum pumping length for the binary string 010 is:
l. The minimum pumping length of the binary string 1* is:
m. Context Free Grammars are closed under Union
5. (18 points) Context Free Grammar Questions Recommended Time: 8-15 minutes
True False
True False True False True False True False True False True False
True False True False True False
01234 0 1 2 3 4 True False
____________
a. Provide the context free grammar below for the language of binary palindromes (binary strings that read the same forwards and backwards).
S → 0 | 1 | 0S0 | 1S1| I will not take off if odd palindromes are not generated.
b. Provide the context free grammar for the language of binary strings that have exactly
one more 1 than 0 (e.g., 01101) S → R1R
R → 0R1 | 1R0 |
c. Provide the context free grammar for binary strings that start and end with different
alphabet symbols (e.g, 0001, 100)
S → 0R1 | 1R0 (empty string not in language so will lose small points for ε in first rule) R →0R | 1R | ε
Page 4 of 7
6. (15 points) Let L be the language of all binary strings where there are at least twice as many 1’s as 0’s. Sample elements of the language include: 011, 110, 11110, 011110111. Use the pumping lemma to prove that this language is not regular. For your convenience, the pumping lemma is provided below.
Recommended time: 3 – 7 minutes
Here is the pumping lemma for regular languages:
If A is a regular language, then there is a number p (the pumping length) where, if s is any string in A of length at least p, then s may be divided into 3 pieces, s = xyz, satisfying the following conditions:
1. Foreachi≥0,xyizA,
2. |y|>0,and
Include your proof below. You should fill in your string s below, since it is needed. Hint: if there is not a p in it you cannot do the proof.
s = __0p12p____________________
By the pumping lemma, there is a pumping length p where we can construct a string s that obeys the 3 conditions listed in the lemma. Let the string be 0p12p. By condition 3, y may only contain 0’s and by condition 2 there must be at least one 0. Thus, when we pump up to get xyyz, there will be at least p+1 0’s, and hence there will no longer be 2 times as many 1’s as 0’s.
You do not need the following, but if you want to be more formal you can say 2(p+1) = 2p+2 > 2p. Thus, the language is not regular.
Below is the minimalist solution, which would receive full credit.
Let s = 0p12p. By condition 3 y may only contain 0’s. Pumping up will break the equality.
Page 5 of 7
(12 points) Convert the following NFA to the equivalent DFA using the procedure we covered in class. Do not simplify the resulting DFA by removing states that are not reachable.
Recommended Time: 5-10 Minutes
Page 6 of 7
b {2} a {}
8. (4 points Extra Credit) Figure (a) below shows the generic outline of an NFA that accepts the language L, where there is a start state and two accept states (the details of internal transitions are not shown). Figure (b) shows a first attempt at implementing L*, the Kleene closure of L. The scheme in Figure (b) almost works, but does not quite work, and hence the slightly more complex solution is Figure (c) is required. In the space below Figure (c) provide a short description for why Figure (b) does not quite work and Figure (c) is required.
ANSWER: A state in the NFA may already loop back to the start state. Thus making the start state an accept state could lead to strings that should not be accepted to be accepts. Thus (b) is incorrect. It can be addressed by part c.
Page 7 of 7
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com