HW3 Solutions (100 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).
Questions related to material in Chapter 1.2
1.7ab (16), 1.8a (8), 1.9b (8), 1.14 (8), and 1.16 (20)
Copyright By PowCoder代写 加微信 powcoder
Questions related to material in Chapter 1.3:
1.12 (10), 1.17a (10), 1.18abcmn (10), 1.20 (0), 1.21a (0), and 1.60 (10)
1.7. Give state diagrams of NFA, with the specified number of states recognizing each of the following languages. In all parts the alphabet is {0,1}
a) The language {w|w ends in 00} with 3 states (8 points)
b) The language where w contains the substring 0101 with 5 states (8 points)
q1 0 0 1 01 0 010 1
Ideally you should not have any unnecessary transitions. Try to exploit the non-determinism.
1.8a) Use the construction given in the proof of Theorem 1.45 to give the state diagrams of NFAs recognizing the union of the language w begins with a 1 and ends with a 0 and w contains at least 3 1’s. (8 points)
1.9b) Using the construction given in the proof of Theorem 1.47 to give the state diagrams of NFAs recognizing the concatenation of the languages w contains at least 3 1’s and the empty set. (8 points)
Since nothing is accepted the NFA could be simplified to almost nothing, but that is not what is asked. If students omit the last loop at the end, take off one point since then they are not using the construction (if they say it is not needed, then neither are 4 of the 5 states so they should simplify all the way).
q1 1 1 1 11 1 111 ε
a) Show that if M is a DFA that recognizes language B, swapping the accept and nonaccept states in M yields a
new DFA that recognizes the complement of B. Conclude that the class of regular languages is closed under complement. (4 points)
Let M’ be the DFA M with the accept and non-accept states swapped. We show that M’ recognizes the complement of B, where B is the language recognized by M. Suppose M’ accepts x. If we run M’ on x we end in an accept state of M’. Because M and M’ have swapped accept/non-accept states, if we run M on x we would end in a non-accept state. Therefore, x B. Similarly, if x is not accepted by M’, then it would be accepted by M. So M’ accepts exactly those string not accepted by M. Therefore M’ recognizes the complement of B.
Since B could be any arbitrary regular language and our construction shows how to build an automaton to recognize its complement, it follows that the complement of any regular language is also regular. Therefore, the class of regular languages is closed under complement.
b) Show by giving an example that, if M is an NFA that recognizes language C, swapping the accept and non- accept stats in M doesn’t necessarily yield a new NFA that recognizes the complement of C. Is the class of languages recognized by NFAs closed under complement? Explain your answer. (4 points)
Consider the NFA below, from exercise 1.16a, shown below. The string a is accepted by this automaton. If we swap the accept and reject states, the string a is still accepted. This shows that swapping the accept and non-accept states of an NFA doesn’t necessarily yield a new NFA recognizing the complementary language. Why? Well, this is an asymmetry. A string is accepted by an NFA if any of the possible paths winds up in an accept state. That means there may be a path that leads to a state that is not an accept state. If we take the complement, that same path will now wind up in an accept state and hence the string will be accepted, even though we do not want it to be.
1 a,b 2 NFA from exercise 1.16a
The class of languages recognized by NFAs is, however, closed under complement. This follows from the fact that the class of languages recognized by NFAs is precisely the class of languages recognized by DFAs which we know is closed under complement from part a. How do we then explain the observed problem, which might appear to be a contradiction? The answer is this: the procedure of swapping the accept and non-accept states to generate the complement works for DFA’s but not NFA’s. However, since the language recognized by NFA’s is closed under complement (from part a), there must be some procedure to generate the complement of an NFA. But we know one! Convert the NFA to a DFA using the procedure we are familiar with and then swap the accept and non-accept states.
1.16 Use the construction given in Theorem 1.9 to convert the following two NFAs to equivalent DFAs.
Note that we need one state for each entry in the power set of the original states. (10 points)
b {2} a {}
You need to handle ε-transitions: When leaving state 2 on an a you go to state 1 but also back to 2, since there is an ε-transition from state 1 to state 2. So, on a state {2} goes to state {1,2}. (10 points)
{} b {1} a {3}
{2,3} a,b b
1.12 Let D = {w| w contains an even number of a’s and an odd number of b’s and does not contain the substring ab}. Give a 5 state DFA that recognizes D and a regular expression that generates D. (10 points)
The trick here is that the condition that there is no substring ab means that all b’s must come first. Thus, we just need to handle an odd number of b’s followed by an even number of a’s. The regular expression is easier: b(bb)*(aa)*. Note that an odd number is an even number plus 1. Here is the DFA with 5 states.
1.17a) Give an NFA recognizing the language (01 001 010)*
The question does not specifically ask the students to use the construction for implementing union, so it is okay if they provide a simpler version of what is shown below, by factoring out the first 0 and then also the first 01. Because there are no loops that go back to the start state without representing a string that is in the language, I also believe they can avoid introducing a new start state. Also, if a student literally uses the construction for concatenation, then there may be additional states, with epsilon moves, within each of the string 01, 001, and 010. Thus, the answer below is not the only acceptable answer.
1.18) (10 points—2 points each)
b. *1*1*1* c. *0101*
m. or {}
n. * or +
{w|w begins with a 1 and ends with a 0} {w|w contains at least three 1’s}
{w|w contains the substring 0101}
The empty set
All strings except the empty string
1.20 (not graded)
a. members: ab, ε;
b. members: ab, abab;
c. members: ε, aa;
d. members: ε, aaa;
e. members: aba, aabbaa;
f. members: aba, bab;
g. members: b, ab;
h. members: ba, bba;
not members: ba, aba not members: ε, aabb not members: ab, aabb not members: aa,b
not members: ε, abbb not members: ε, ababab not members: ε, bb
not members: b, ε
1.21a. (not graded)
Don’t worry about using their procedure. Just try to create one. Here is one answer: a*b(aba*b)*
1.60. (10 points)
The NFA N guesses when it has read an a that appears k symbols from the end, then counts k-1 more symbols and enters an accept state. It has an initial state q0 and additional states q1 to qk. State q0 has transitions on both a and b back to itself and on a to q1. For 1 ≤ i ≤ k – 1, state qi has transitions on a and b to state qi+1. State qk is an accept state with no transition arrows coming out of it.
Or more formally:
(Start state q0)
Q = {q0, q1, …, qk} = {a, b}
δ(qi, c) =
if i=0 and c = a
{qi+1} if 1 < i < k and c = if i = k of c
if i=0 and c = b
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com