CS 1502 — Formal Methods in Computer Science Assignment 1
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.
2022-09-16