CSE311-Homework 8 Solved

1.     State of the Art [Online]
For each of the following, create an NFA that recognizes exactly the language described.

(a)      Binary strings with at least three 1s or an odd number of 0s.

(b)     Binary strings with at least three 1s and ending in 010.

2.     Regular as Clockwork [Online]
For each of the following regular expressions, create an NFA that recognizes the same language. (a) ((0 ∪ 11)∗00)∗

(b)  (1 ∪ 01 ∪ 001)∗(ε ∪ 0 ∪ 00)

3.     State’s Evidence [Online]
Use the construction from lecture to convert each of the following NFAs to DFAs.

Label each state of the DFA with the corresponding states of the NFA. For example, if the state corresponds to {q0,q1,q3}, then label the state “q0,q1,q3”. The empty state can be labeled “empty set” or similar. (a)  The NFA below, which we get by applying the construction described in class[1] to the regular

 

(b) The NFA below:

 

4.     Enemy of the State
Use the algorithm for minimization that we discussed in class to minimize the each of the following DFAs.

(a)     Your solution to Problem 3 (a), which should be a DFA. (Make sure you first submit your solution to that problem and ensure that it is correct before solving this problem.)

You may want to start by renaming the states of that machine since we originally gave them large names, corresponding to the subset of NFA states that they represent.

(b)     

 

5.     Not Again
Let A = {...,p,q,r,...} be a fixed set of atomic propositions. We then define the set Prop as follows:

Basis Elements For any p ∈ A, Atomic(p) ∈ Prop.

Recursive Step If A,B ∈ Prop, then NOT(A) ∈ Prop and XOR(A,B) ∈ Prop.

The set Prop represents parse trees of propositions that use only the operations of negation (represented by NOT) and exclusive or (represented by XOR).

Next, we define a function T that takes a parse tree (an element of Prop) as input and returns the proposition that it represents. Formally, we define

T (Atomic(p)) = p
for any p ∈ A
T (NOT(A)) = ¬T (A)
for any A ∈ Prop
                                     T (XOR(A,B)) = (T (A)) ⊕ (T (B))                                      for any A,B ∈ Prop

(Note that this setup is very similar to that of Problem 5 from Section 8. The only differences are that these parse trees support “⊕” rather than “∧” and “∨”.)

Now, let p ∈ A be any atomic proposition. The function negp takes a parse tree as input and returns another parse tree with all nodes representing p replaced by nodes representing ¬p instead:

negp(Atomic(q)) = NOT(Atomic(q)) if q = p negp(Atomic(q)) = Atomic(q) for any q ∈ A with q 6= p negp(NOT(A)) = NOT(negp(A)) for any A ∈ Prop

                               negp(XOR(A,B)) = XOR(negp(A),negp(B))                               for any A,B ∈ Prop

(a)     Prove the following: for any A ∈ Prop and any p ∈ A, we have either T (negp(A)) ≡ T (A) or T (negp(A)) ≡ ¬T (A).

Note that some facts proven in Problem 4 of Section 2 may be useful here.

(b)    Let A ∈ Prop be an expression using only the atomic variables p,q ∈ A. What do we know about the truth table of T (A) in the case that T (negp(A)) = T (A)? How about if T (negp(A)) = ¬T (A)?

(c)     ] We saw in lecture that ¬, ∨, and ∧ together can express any proposition (e.g., by writing it in sum-of-products form). De Morgan’s Law tells us that ∧ can be written instead with ∨, so any proposition can be expressed with only ¬ and ∨. Prove that the same is not true of ¬ and ⊕.

Specifically, use the results of the earlier parts to show that p ∧ q cannot be represented by any expression using only ¬ and ⊕.

6.     Just Irregular Guy
Use the method described in lecture to prove that each of the following languages is not regular.

(a)     The set of binary strings of the form {0x1m0y | x,m,y > 1 and x ≡ y (mod m)}.

(b)    Unicode strings that are syntactically valid Java Script Object Notation (JSON). (This simple language does not include arithmetic expressions but is already irregular.)

7.     Extra Credit: Pratt-Pratt-Pratt
Suppose we want to determine whether a string x of length n contains a string y = y1y2 ...ym with  .

To do so, we construct the following NFA:

 

                                    0,1                                                                                                                                                                            0,1

(where the ... includes states s3,...,sm−2). We can see that this NFA matches x iff x contains the string y.

We could check whether this NFA matches x using the parallel exploration approach, but doing so would take O(mn) time, no better than the obvious brute-force approach for checking if x contains y. Alternatively, we can convert the NFA to a DFA and then run the DFA on the string x. A priori, the number of states in the resulting DFA could be as large as 2m, giving an Ω(2m + n) time algorithm, which is unacceptably slow. However, below, you will show that this approach can be made to run in O(m[2]+ n) time.

(a)     Consider any subset of states, S, found while converting the NFA above into a DFA. Prove that, for each 1 ≤ j < m, knowing sj ∈ S functionally determines whether si ∈ S or not for each 1 ≤ i < j.

(b)    Explain why this means that the number of subsets produced in the construction is at most 2m.

(c)     Explain why the subset construction thus runs in only O(m2) time (assuming the alphabet size is O(1)).

(d)    How many states would this reduce to if we then applied the state minimization algorithm?

(e)     Explain why part (c) leads to a bound of O(m2+ n) for the full algorithm (without state minimization).

(f)      Briefly explain how this approach can be modified to count (or, better yet, find) all the substrings matching y in the string x with the same overall time bound.

Note that any string matching algorithm takes Ω(m + n) = Ω(n) time in the worst case since it must read the


 
[1] The only simplification performed was using three states rather than four to represent the sub-expression 00.
[2] = O(n), or equivalently, m = O(√n), which entire input. Thus, the above algorithm is optimal whenever m is the case for normal inputs circumstances.