Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CS 1502 — Formal Methods in Computer Science

Assignment 1 (100 points)

1 (10 points) The formal description of a DFA M is (nq1 , q2 , q3 , q4 , q5 }, nu, d}, δ, q3 , nq3 }),

where δ is given by the following table. Let L(M) be the language of this machine M . Answer the following questions:

u     d

q2

q3

q4

q5

q5

(a)  (8 points) Give the state diagram of the above machine

(b)  (1 point) Give an example of a string that is a member of L(M)

(c)  (1 point) Give an example of a string that is NOT a member of L(M)

2 (10 points) Let Σ = n0, 1} and let v(w) be the value of w in decimal where w is a

string of unsigned binary.  For examples, v(0010) = 2 and v(011010) = 26.  Note that v(ε) is undefined. Let

A = nw | w such that 2 5 v(w) 5 5}.

For example,

. 0100 – accept since v(0100) = 4,

. 0000110 – reject since v(0000110) = 6,

.  1101 reject since v(1101) = 13 and

. 000000011 – accept since v(000000011) = 3.

Create a state diagram of a machine that recognizes A.

3 (10 points) Let Σ = n0, 1}. Give state diagrams of DFAs recognizing the languages: nw | w begins with a 1 and ends with a 0}

4 (40 points) Let Σ = na, b}. Consider the language

A = nw | w has an even number of a’s and one or two b’s}

Note that the languages A is the intersection of two simpler languages,  B  and C . Formally, A = B ∩ C . Answer the following questions:

(a)  (5 points) What is the description of the language B in the form of nw | . . . }? (b)  (10 points) Give a state diagram of a DFA that recognizes the language B       (c)  (5 points) What is the description of the language C in the form of nw | . . . }?

(d)  (10 points) Give a state diagram of a DFA that recognizes the language C

(e)  (10 points) Combine both machines using the method discussed in class to

obtain a DFA that recognizes the language A = B C

5 (15 points) Let Σ = na, b}. Consider the following language:

A = nw | w contains neither the substrings ab nor ba}

Answer the following questions:

(a)  (5 points) What is the description of the language A  (the complement of the

language A) in the form of A = nw |  . . . }?

(b)  (5 points) Give a state diagram of a DFA that recognizes A

(c)  (5 points) Convert your state diagram of a DFA that recognizes the language A into a new state diagram of a DFA that recognize the language A using the method discussed in class.

6 (15 points) Let Σ = na, b}. Consider the following language:

B = nw | w is any string that doesn’t contain exactly two a’s}

Answer the following questions:

(a)  (5 points) What is the description of the language  B  (the complement of the

language B) in the form of B = nw |  . . . }?

(b)  (5 points) Give a state diagram of a DFA that recognizes B

(c)  (5 points) Convert your state diagram of a DFA that recognizes the language B into a new state diagram of a DFA that recognize the language B using the method discussed in class.