Midterm MM Co2011 Hk231 en Da

Lecturer: October 2nd, 2023 Approved by: October 2nd, 2023
(Signature and Fullname) (Signature and Fullname)
Semester/Academic year 1 2023-2024

MIDTERM
Date 18/10/2023
Course title Mathematical Modeling
UNIVERSITY OF TECHNOLOGY Course ID CO2011
FACULTY OF CSE Duration 60 mins Question sheet code 1811
Notes: - Students do not use course materials except one A4 hand-written sheet.
- Submit the question sheet together with the answer sheet.
- Choose the best answer (only 1) for each question.
1. (L.O.1.2)
Which of the following statements is/are true?
(I) All finite languages are regular.
(II) If L is regular so is the reverse language LR = {wR |w ∈ L}.
(III) L = {ww|w ∈ {a, b}∗ } is regular.
c = (Q, Σ, δ, q0 , Q − F ) is a
(IV) If M = (Q, Σ, δ, q0 , F ) is a minimal DFA for a regular language L then M
minimal DFA for L.
A. (I), (II), (III). B. (I), (II), (IV). C. Only (I). D. (II), (III), (IV).
2. (L.O.1.3) Given a program finding max for 3 integers a,b,c:

max=0;
if(max<a) max=a;
if(max<b) max=b;
if(max<c) max=c;
Which of the following are the weakest pre-condition ϕ and post-condition ψ for the program to be correct?
A. ϕ : a, b, c >= 0, ψ : a = 0, ψ : a, b, c ≤ max

C. ϕ : a, b, c > 0, ψ : a, b, c ≤ max D. ϕ : T , ψ : a, b, c ≤ max
Stu.ID: .......................................... Stu.Fullname: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Code: 1811 Page: 1/6

3. Consider a program Prod = P roduct(a, b) calculating the product a · (b − 1) of two naturals a, b where b ≥ 2.
Denote the Hoare triple of a suitable core program P to correctly compute Prod as
{ϕ} P {ψ}
where pre-conditions ϕ := (a ≥ 1) ∧ (b ≥ 2) and post-conditions ψ should be suitably defined. A variant K

is an expression whose values are either strictly decreasing or strictly decreasing, and an invariant E does
not change its Boolean value in the loop. Both K and E depend on original inputs a, b and also internal
variables being newly declared in the program. Conditions and such variants are put in brackets {..}.
Let E = { u = (b − v) · a} be a “good” invariant of the program Prod, assuming the full format as follows.
{(a ≥ 1) ∧ (b ≥ 2)}
u = 0;
v = b;
{u = 0 ∧ v = b}
E
while ( v != Lb )
{
..
.P
}
{u = a · (b − v)}
In the following options of core program P and lower bound Lb:

(I) P := [u = u + a; v = v − 1; ] and Lb := 0
(II) P := [u = u + a; v = v − 2; ] and Lb := 1
Which one do you choose to obtain the totally correct
(III) P := [u = u + a; v = v − 1; ] and Lb := 1
(IV) P := [u = u + a; v = v + 1; ] and Lb := 1.
statement?
⊢tot {ϕ} Prod {u = a · (b − 1)}?
A. (IV) B. (III) C. (II) D. (I)

4. (L.O.2.3) Given 4 automata where Σ = {a, b} and λ is the empty string.
Which of the following couples are the same?

A. 1,2 B. 1,3 C. 3,4
D. All the other answers are incorrect.
5. (L.O.2.3) Let L be the language consisting of string w ∈ {0, 1}+ that represents a decimal number divisible
by 3. Which choice is CORRECT?
A. All other choices are incorrect.
B. L is not a regular language.
C. The number of states of a DFA recognizing only L must be divisible by 3.
D. The number of bit 1s of any string of L must be divisible by 3.
6. (L.O.1.3) Given a post-condition for a correct program:

[|∀q(i < q ≤ n =⇒ a[i] ≤ a[q]) ∧ a[i] ≤ a[i − 1]|]
Which of the following post-conditions also correct for the same program?
A. [|∀q(i − 1 < q ≤ n =⇒ a[i − 1] ≤ a[q])|] B. [|∀q(i ≤ q ≤ n =⇒ a[i] ≤ a[q])|]
C. [|∀q(i < q ≤ n =⇒ a[i − 1] ≤ a[q])|] D. All the other answers are correct.
7. (L.O.1.3)
Consider program P with precondition and postcondition as in Question 8. Then the invariant form to prove
the partial correctness of P is
A. z ∈ Z ∧ yxz = ab . B. z ∈ N ∧ yxz = ab . C. z ∈ N ∧ y = xz . D. z ∈ Z ∧ y = xz .

8. (L.O.3.2)
Consider the following finite automaton:
a a
A B C a
b b
a
a E b
b
a b
b D G a F
b
What is the number of states in a minimal DFA (equivalent to the above FA)?
A. 4. B. 5. C. 6. D. 7.
9. (L.O.2.3) Let L be the language containing all the palindrome words where Σ = {a, b}, Which of the following
regular expressions accepts the words in language L?
A. (a+b)*(b+a)* B. a*b*b*a* C. (abba)*
10. (L.O.2.3) Let L be the language consisting of string w ∈ {0, 1}∗ that the number of occurrences of sub-string
01 and the number of occurrences of sub-string 10 in w are the same. Which choice is CORRECT?
A. A DFA recognizing only L must have at least five states.
B. L is not a regular language.
C. The number of bit 1s and the number of bit 0s of any string of L must be the same.
D. All other choices are incorrect.
11. (L.O.1.2)
Consider the logical formula ϕ : ∀x∃y∃z(P (x, y) ∧ P (z, y) ∧ (P (x, z) → P (z, x))) and the models M1 , M2 and
M3 such that the universal set is the natural numbers set N, P M1 = {(m, n)|n < m}, P M2 = {(m, 2m)|m ∈
N} and P M3 = {(m, n)|m < n + 1} Which of following statement is true?
A. M1 |= ϕ, M2 |̸ = ϕ, M3 |̸ = ϕ. B. M1 |= ϕ, M2 |= ϕ, M3 |= ϕ.
C. M1 |̸ = ϕ, M2 |= ϕ, M3 |= ϕ. D. M1 |̸ = ϕ, M2 ̸|= ϕ, M3 |= ϕ.
12. (L.O.1.3)
Given the following program, with ⊤ as a precondi-

tion, determine the postcondition yourself. To prove
the partial correctness of the corresponding Hoare
triple, which of the following is an invariant form we
should use?
(i−1)/2 i/2
X X
A. s = 2k ∧ (i ≤ n + 1). B. s = 2k ∧ (i ≤ n).
k=0 k=0
(i−1)/2 i/2
X X
C. s = 2k. D. s = 2k ∧ (i ≤ n + 1).
k=0 k=0
Question 13– Question 14 use the same description as follows: Denote an alphabet Σ = {b, c}, and let u = bc,
v = cb be strings of length 2 in Σ∗ . Define L(r) and L(s) respectively be languages determined by regular expressions

r = u∗ = (bc)∗ and s = v ∗ = (cb)∗ .
13. The language Lbc of all strings with b and c alternating, moreover starting with b and ending with c, is
(I) L(s); (II) L(r) + L(s); (III) L(r); (IV) L(r) · L(s).
A. (III) B. (IV) C. (II) D. (I)
14. The language L of all strings with b and c alternating is determined by which of the following regular
expressions?
(I) r + s; (II) r + s + c r + b s; (III) r + s + b r + c s; (IV) s + r.
A. IV B. III C. II D. I
15. Consider the following statement: “A female athlete won every sports prize and her brother also
won some mathematics prize.” We define some predicates below to symbolize the given statement
• Girl(a) = “a is a girl”, Boy(b) = “b is a boy”,
• SportP rize(x) = “x is a prize in Sport tournament”,
• M athP rize(y) = “y is a prize in Mathematics competition”,
• Sibling(a, b) = “a and b are siblings in a family”,
• W inSport(w, s) = “w won a sport prize s”,
• W inM ath(u, m) = “u won a mathematics prize m”.
Which of the following options best represents the given statement?
(I) ∀x [SportP rize(x) −→ ∃y (Girl(y) ∧ W inSport(y, x))]
(II) [ (∃f, Girl(f ) ∧ ∀x, SportP rize(x)) −→ W inSport(f, x) ]

∧ [ (∃b, Sibling(f, b) ∧ Boy(b) ∧ ∃y, M athP rize(y)) −→ W inM ath(b, y)]
(III) ∃f [ (Girl(f ) ∧ ∀x, SportP rize(x)) −→ W inSport(f, x) ]

∧ ∃m [ (Sibling(f, m) ∧ ∃y, M athP rize(y)) −→ W inM ath(m, y) ]
(IV) ∃f [ (Girl(f ) ∧ ∀x, SportP rize(x)) −→ W inSport(f, x) ]

∧ ∃m [ (Sibling(f, m) ∧ Boy(m) ∧ ∃y, M athP rize(y)) −→ W inM ath(m, y) ]
A. (IV) B. (III) C. (II) D. (I)
16. (L.O.1.3)
In the following program, % is the division with

remainder and returns the remainder, and function
abs() returns the absolute value of an input integer.
Consider the precondition x = x0 ∧ y = y0 ∧ (x0 ̸=
0 ∨ y0 ̸= 0). Which is the invariant form for proving
the partial correctness of the program? [In the choices,
GCD(a, b) denotes the greatest common divisor of two
integers a and b that are not both 0, a mod b is the
division with the remainder by positive b and |a| is
the absolute value of a.]
A. GCD(x, y) = GCD(x0 , y0 ) B. y ̸= 0 → GCD(x, x mod |y|) = GCD(x0 , y0 )

C. x ̸= 0 → GCD(y, y mod |x|) = GCD(x0 , y0 ) D. All other choices are correct.

17. (L.O.2.3) Which of the following is correct?
A. Given two languages L1 , L2 , if L1 ∪ L2 is regular then both L1 , L2 are also regular.
B. For two languages L1 , L2 , we have L∗1 ◦ L∗2 ⊆ (L1 ∪ L2 )∗ .
C. If L1 , L2 , are finite languages then |L1 ◦ L2 | = |L1 | · |L2 |.
D. If L1 is a regular language and the language L2 is not regular then L◦1 L2 is not regular.
18. (L.O.1.3)
Consider program P below. (Weakest) precondition ϕ

and postcondition ψ of P are
A. ϕ = {a ∈ R, b ∈ N}, ψ = {y = ab }. B. ϕ = {a ∈ R, b ∈ N}, ψ = {y = xz }.
C. ϕ = {a ∈ R, b ∈ Z+ }, ψ = {y = ab }. D. ϕ = {a ∈ R, b ∈ Z}, ψ = {y = ab }.
19. (L.O.1.1) Let P and Q be binary predicates and S be nullary predicates. Which formulas are valid?
(I) ∀x∀y(P (x) → P (y)) ∧ (P (y) → P (x)) (II) ∃y((∀xP (x)) → P (y))
(III) (∀xP (x) → S) → ∃x(P (x) → S) (IV) ∀x(P (x) ∨ Q(x)) → (∀xP (x)) ∨ (∃xQ(x))
A. Only (II), (III), and (IV) B. Only (II) and (III)
C. Only (I), (II), and (IV) D. Only (III) and (IV)
20. (L.O.2.3) Which of the following languages is accepted by the DFA over Σ = {0, 1, 2} given below?
A. L = {w ∈ Σ∗ | w contains exactly two 2′ s}. B. L = {w ∈ Σ∗ | w contains at least two 2′ s}.

C. L = {w ∈ Σ∗ | w contains at most two 2′ s}. D. L = {w ∈ Σ∗ | w contains at least two 2’s consecutively}.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . END OF EXAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Solution 1811
1. B. 7. B. 12. A. 16. A.
2. D. 8. B. 17. B.
3. B. 13. A.
9. A. 18. B.
4. A. 14. C.
5. A. 10. A. 19. A.
6. D. 11. B. 15. A. 20. A.


MIDTERM
Date 18/10/2023
1. (L.O.1.2)
c = (Q, Σ, δ, q0 , Q − F ) is a
minimal DFA for L.
A. (II), (III), (IV). B. (I), (II), (III). C. (I), (II), (IV). D. Only (I).
2. (L.O.1.3)

should use?
i/2 (i−1)/2
X X
A. s = 2k ∧ (i ≤ n + 1). B. s = 2k ∧ (i ≤ n + 1).
k=0 k=0
i/2 (i−1)/2
X X
C. s = 2k ∧ (i ≤ n). D. s = 2k.
k=0 k=0

{ϕ} P {ψ}

{(a ≥ 1) ∧ (b ≥ 2)}
u = 0;
v = b;
{u = 0 ∧ v = b}
E
while ( v != Lb )
{
..
.P
}
{u = a · (b − v)}

(I) P := [u = u + a; v = v − 1; ] and Lb := 0
(II) P := [u = u + a; v = v − 2; ] and Lb := 1
(III) P := [u = u + a; v = v − 1; ] and Lb := 1
(IV) P := [u = u + a; v = v + 1; ] and Lb := 1.
statement?
⊢tot {ϕ} Prod {u = a · (b − 1)}?
A. (I) B. (IV) C. (III) D. (II)

[|∀q(i < q ≤ n =⇒ a[i] ≤ a[q]) ∧ a[i] ≤ a[i − 1]|]
A. All the other answers are correct. B. [|∀q(i − 1 < q ≤ n =⇒ a[i − 1] ≤ a[q])|]
C. [|∀q(i ≤ q ≤ n =⇒ a[i] ≤ a[q])|] D. [|∀q(i < q ≤ n =⇒ a[i − 1] ≤ a[q])|]
A. Only (III) and (IV) B. Only (II), (III), and (IV)
C. Only (II) and (III) D. Only (I), (II), and (IV)

max=0;
if(max<a) max=a;
if(max<b) max=b;
if(max<c) max=c;
A. ϕ : T , ψ : a, b, c ≤ max B. ϕ : a, b, c >= 0, ψ : a = 0, ψ : a, b, c ≤ max D. ϕ : a, b, c > 0, ψ : a, b, c ≤ max




A. (I) B. (IV) C. (III) D. (II)
Question 8– Question 9 use the same description as follows: Denote an alphabet Σ = {b, c}, and let u = bc, v = cb
be strings of length 2 in Σ∗ . Define L(r) and L(s) respectively be languages determined by regular expressions
r = u∗ = (bc)∗ and s = v ∗ = (cb)∗ .
A. (I) B. (III) C. (IV) D. (II)

expressions?
A. I B. IV C. III D. II
A. L = {w ∈ Σ∗ | w contains at least two 2’s consecutively}.

B. L = {w ∈ Σ∗ | w contains exactly two 2′ s}. C. L = {w ∈ Σ∗ | w contains at least two 2′ s}.
D. L = {w ∈ Σ∗ | w contains at most two 2′ s}.
A. All the other answers are incorrect. B. (a+b)*(b+a)* C. a*b*b*a*
D. (abba)*

12. (L.O.1.3)

A. ϕ = {a ∈ R, b ∈ Z}, ψ = {y = ab }. B. ϕ = {a ∈ R, b ∈ N}, ψ = {y = ab }.
C. ϕ = {a ∈ R, b ∈ N}, ψ = {y = xz }. D. ϕ = {a ∈ R, b ∈ Z+ }, ψ = {y = ab }.
13. (L.O.1.3)
A. z ∈ Z ∧ y = xz . B. z ∈ Z ∧ yxz = ab . C. z ∈ N ∧ yxz = ab . D. z ∈ N ∧ y = xz .

A. All the other answers are incorrect. B. 1,2 C. 1,3 D. 3,4
A. The number of bit 1s of any string of L must be divisible by 3.
B. All other choices are incorrect.
C. L is not a regular language.
D. The number of states of a DFA recognizing only L must be divisible by 3.

B. A DFA recognizing only L must have at least five states.
D. The number of bit 1s and the number of bit 0s of any string of L must be the same.
A. If L1 is a regular language and the language L2 is not regular then L◦1 L2 is not regular.
B. Given two languages L1 , L2 , if L1 ∪ L2 is regular then both L1 , L2 are also regular.
C. For two languages L1 , L2 , we have L∗1 ◦ L∗2 ⊆ (L1 ∪ L2 )∗ .
D. If L1 , L2 , are finite languages then |L1 ◦ L2 | = |L1 | · |L2 |.
18. (L.O.1.3)

A. All other choices are correct. B. GCD(x, y) = GCD(x0 , y0 )

C. y ̸= 0 → GCD(x, x mod |y|) = GCD(x0 , y0 ) D. x ̸= 0 → GCD(y, y mod |x|) = GCD(x0 , y0 )
19. (L.O.1.2)
A. M1 ̸|= ϕ, M2 |̸ = ϕ, M3 |= ϕ. B. M1 |= ϕ, M2 |̸ = ϕ, M3 |̸ = ϕ.
C. M1 |= ϕ, M2 |= ϕ, M3 |= ϕ. D. M1 |̸ = ϕ, M2 |= ϕ, M3 |= ϕ.
20. (L.O.3.2)
a a
A B C a
b b
a
a E b
b
a b
b D G a F
b
A. 7. B. 4. C. 5. D. 6.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . END OF EXAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Solution 1812
1. C. 7. B. 11. B. 17. C.
2. B. 12. C.
18. B.
3. C. 8. B. 13. C.
4. A. 9. D. 14. B.
19. C.
5. B. 15. B.
6. A. 10. B. 16. B. 20. C.


MIDTERM
Date 18/10/2023
1. (L.O.1.3)

A. ϕ = {a ∈ R, b ∈ N}, ψ = {y = ab }. B. ϕ = {a ∈ R, b ∈ Z}, ψ = {y = ab }.
C. ϕ = {a ∈ R, b ∈ N}, ψ = {y = xz }. D. ϕ = {a ∈ R, b ∈ Z+ }, ψ = {y = ab }.


A. 1,2 B. All the other answers are incorrect. C. 1,3 D. 3,4

max=0;
if(max<a) max=a;
if(max<b) max=b;
if(max<c) max=c;
A. ϕ : a, b, c >= 0, ψ : a = 0, ψ : a, b, c ≤ max D. ϕ : a, b, c > 0, ψ : a, b, c ≤ max

4. (L.O.3.2)
a a
A B C a
b b
a
a E b
b
a b
b D G a F
b
A. 4. B. 7. C. 5. D. 6.
5. (L.O.1.2)
A. M1 |= ϕ, M2 |̸ = ϕ, M3 |̸ = ϕ. B. M1 ̸|= ϕ, M2 |̸ = ϕ, M3 |= ϕ.
C. M1 |= ϕ, M2 |= ϕ, M3 |= ϕ. D. M1 |̸ = ϕ, M2 |= ϕ, M3 |= ϕ.
6. (L.O.1.2)
c = (Q, Σ, δ, q0 , Q − F ) is a
minimal DFA for L.
A. (I), (II), (III). B. (II), (III), (IV). C. (I), (II), (IV). D. Only (I).

B. If L1 is a regular language and the language L2 is not regular then L◦1 L2 is not regular.
D. If L1 , L2 , are finite languages then |L1 ◦ L2 | = |L1 | · |L2 |.




A. (IV) B. (I) C. (III) D. (II)
A. L = {w ∈ Σ∗ | w contains exactly two 2′ s}. B. L = {w ∈ Σ∗ | w contains at least two 2’s consecutively}.

C. L = {w ∈ Σ∗ | w contains at least two 2′ s}. D. L = {w ∈ Σ∗ | w contains at most two 2′ s}.
B. The number of bit 1s of any string of L must be divisible by 3.
D. The number of states of a DFA recognizing only L must be divisible by 3.
11. (L.O.1.3)
A. z ∈ Z ∧ yxz = ab . B. z ∈ Z ∧ y = xz . C. z ∈ N ∧ yxz = ab . D. z ∈ N ∧ y = xz .

12. (L.O.1.3)

A. GCD(x, y) = GCD(x0 , y0 ) B. All other choices are correct.

C. y ̸= 0 → GCD(x, x mod |y|) = GCD(x0 , y0 ) D. x ̸= 0 → GCD(y, y mod |x|) = GCD(x0 , y0 )
13. (L.O.1.3)

should use?
(i−1)/2 i/2
X X
A. s = 2k ∧ (i ≤ n + 1). B. s = 2k ∧ (i ≤ n + 1).
k=0 k=0
i/2 (i−1)/2
X X
C. s = 2k ∧ (i ≤ n). D. s = 2k.
k=0 k=0

[|∀q(i < q ≤ n =⇒ a[i] ≤ a[q]) ∧ a[i] ≤ a[i − 1]|]
A. [|∀q(i − 1 < q ≤ n =⇒ a[i − 1] ≤ a[q])|] B. All the other answers are correct.
C. [|∀q(i ≤ q ≤ n =⇒ a[i] ≤ a[q])|] D. [|∀q(i < q ≤ n =⇒ a[i − 1] ≤ a[q])|]
A. Only (II), (III), and (IV) B. Only (III) and (IV)
C. Only (II) and (III) D. Only (I), (II), and (IV)
r = u∗ = (bc)∗ and s = v ∗ = (cb)∗ .
A. (III) B. (I) C. (IV) D. (II)

expressions?
A. IV B. I C. III D. II

{ϕ} P {ψ}

{(a ≥ 1) ∧ (b ≥ 2)}
u = 0;
v = b;
{u = 0 ∧ v = b}
E
while ( v != Lb )
{
..
.P
}
{u = a · (b − v)}

(I) P := [u = u + a; v = v − 1; ] and Lb := 0
(II) P := [u = u + a; v = v − 2; ] and Lb := 1
(III) P := [u = u + a; v = v − 1; ] and Lb := 1
(IV) P := [u = u + a; v = v + 1; ] and Lb := 1.
statement?
⊢tot {ϕ} Prod {u = a · (b − 1)}?
A. (IV) B. (I) C. (III) D. (II)
D. The number of bit 1s and the number of bit 0s of any string of L must be the same.
A. (a+b)*(b+a)* B. All the other answers are incorrect. C. a*b*b*a*
D. (abba)*
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . END OF EXAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Solution 1813
1. C. 6. C. 11. C. 16. A.
2. A. 7. C. 12. A. 17. D.
13. A.
3. B. 8. A.
18. C.
14. B.
4. C. 9. A. 19. A.
15. A.
5. C. 10. A. 20. A.


MIDTERM
Date 18/10/2023
1. (L.O.1.2)
A. M1 |= ϕ, M2 |̸ = ϕ, M3 |̸ = ϕ. B. M1 ̸|= ϕ, M2 |= ϕ, M3 |= ϕ.
C. M1 |= ϕ, M2 |= ϕ, M3 |= ϕ. D. M1 |̸ = ϕ, M2 ̸|= ϕ, M3 |= ϕ.
A. (a+b)*(b+a)* B. (abba)* C. a*b*b*a*
max=0;
if(max<a) max=a;
if(max<b) max=b;
if(max<c) max=c;
A. ϕ : a, b, c >= 0, ψ : a 0, ψ : a, b, c ≤ max

C. ϕ : a, b, c >= 0, ψ : a, b, c ≤ max D. ϕ : T , ψ : a, b, c ≤ max
4. (L.O.1.2)
c = (Q, Σ, δ, q0 , Q − F ) is a
minimal DFA for L.
A. (I), (II), (III). B. Only (I). C. (I), (II), (IV). D. (II), (III), (IV).
B. The number of bit 1s and the number of bit 0s of any string of L must be the same.

6. (L.O.3.2)
a a
A B C a
b b
a
a E b
b
a b
b D G a F
b
A. 4. B. 6. C. 5. D. 7.
r = u∗ = (bc)∗ and s = v ∗ = (cb)∗ .
A. (III) B. (II) C. (IV) D. (I)
expressions?
A. IV B. II C. III D. I
B. The number of states of a DFA recognizing only L must be divisible by 3.

[|∀q(i < q ≤ n =⇒ a[i] ≤ a[q]) ∧ a[i] ≤ a[i − 1]|]
A. [|∀q(i − 1 < q ≤ n =⇒ a[i − 1] ≤ a[q])|] B. [|∀q(i < q ≤ n =⇒ a[i − 1] ≤ a[q])|]
C. [|∀q(i ≤ q ≤ n =⇒ a[i] ≤ a[q])|] D. All the other answers are correct.
11. (L.O.1.3)
A. z ∈ Z ∧ yxz = ab . B. z ∈ N ∧ y = xz . C. z ∈ N ∧ yxz = ab . D. z ∈ Z ∧ y = xz .


A. 1,2 B. 3,4 C. 1,3

{ϕ} P {ψ}

{(a ≥ 1) ∧ (b ≥ 2)}
u = 0;
v = b;
{u = 0 ∧ v = b}
E
while ( v != Lb )
{
..
.P
}
{u = a · (b − v)}

(I) P := [u = u + a; v = v − 1; ] and Lb := 0
(II) P := [u = u + a; v = v − 2; ] and Lb := 1
(III) P := [u = u + a; v = v − 1; ] and Lb := 1
(IV) P := [u = u + a; v = v + 1; ] and Lb := 1.
statement?
⊢tot {ϕ} Prod {u = a · (b − 1)}?
A. (IV) B. (II) C. (III) D. (I)
A. Only (II), (III), and (IV) B. Only (I), (II), and (IV)
C. Only (II) and (III) D. Only (III) and (IV)
15. (L.O.1.3)

A. ϕ = {a ∈ R, b ∈ N}, ψ = {y = ab }. B. ϕ = {a ∈ R, b ∈ Z+ }, ψ = {y = ab }.
C. ϕ = {a ∈ R, b ∈ N}, ψ = {y = xz }. D. ϕ = {a ∈ R, b ∈ Z}, ψ = {y = ab }.

16. (L.O.1.3)

should use?
(i−1)/2 (i−1)/2
X X
A. s = 2k ∧ (i ≤ n + 1). B. s = 2k.
k=0 k=0
i/2 i/2
X X
C. s = 2k ∧ (i ≤ n). D. s = 2k ∧ (i ≤ n + 1).
k=0 k=0
17. (L.O.1.3)

A. GCD(x, y) = GCD(x0 , y0 ) B. x ̸= 0 → GCD(y, y mod |x|) = GCD(x0 , y0 )

C. y ̸= 0 → GCD(x, x mod |y|) = GCD(x0 , y0 ) D. All other choices are correct.




A. (IV) B. (II) C. (III) D. (I)

B. If L1 , L2 , are finite languages then |L1 ◦ L2 | = |L1 | · |L2 |.
A. L = {w ∈ Σ∗ | w contains exactly two 2′ s}. B. L = {w ∈ Σ∗ | w contains at most two 2′ s}.

C. L = {w ∈ Σ∗ | w contains at least two 2′ s}. D. L = {w ∈ Σ∗ | w contains at least two 2’s consecutively}.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . END OF EXAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Solution 1814
1. C. 6. C. 10. D. 16. A.
2. A. 11. C. 17. A.
7. A. 12. A.
3. D. 18. A.
8. B. 13. C.
4. C. 14. A. 19. C.
5. A. 9. A. 15. C. 20. A.


MIDTERM
Date 18/10/2023
r = u∗ = (bc)∗ and s = v ∗ = (cb)∗ .
A. (I) B. (III) C. (II) D. (IV)
expressions?
A. I B. IV C. II D. III



A. (I) B. (IV) C. (II) D. (III)

A. L = {w ∈ Σ∗ | w contains at least two 2’s consecutively}.

B. L = {w ∈ Σ∗ | w contains exactly two 2′ s}. C. L = {w ∈ Σ∗ | w contains at most two 2′ s}.
∗ ′
D. L = {w ∈ Σ | w contains at least two 2 s}.

[|∀q(i < q ≤ n =⇒ a[i] ≤ a[q]) ∧ a[i] ≤ a[i − 1]|]
A. All the other answers are correct. B. [|∀q(i − 1 < q ≤ n =⇒ a[i − 1] ≤ a[q])|]
C. [|∀q(i < q ≤ n =⇒ a[i − 1] ≤ a[q])|] D. [|∀q(i ≤ q ≤ n =⇒ a[i] ≤ a[q])|]
6. (L.O.1.3)

should use?
i/2 (i−1)/2
X X
A. s = 2k ∧ (i ≤ n + 1). B. s = 2k ∧ (i ≤ n + 1).
k=0 k=0
(i−1)/2 i/2
X X
C. s = 2k. D. s = 2k ∧ (i ≤ n).
k=0 k=0
D. L is not a regular language.

max=0;
if(max<a) max=a;
if(max<b) max=b;
if(max<c) max=c;
A. ϕ : T , ψ : a, b, c ≤ max B. ϕ : a, b, c >= 0, ψ : a 0, ψ : a, b, c ≤ max D. ϕ : a, b, c >= 0, ψ : a, b, c ≤ max
9. (L.O.1.3)
A. z ∈ Z ∧ y = xz . B. z ∈ Z ∧ yxz = ab . C. z ∈ N ∧ y = xz . D. z ∈ N ∧ yxz = ab .

10. (L.O.3.2)
a a
A B C a
b b
a
a E b
b
a b
b D G a F
b
A. 7. B. 4. C. 6. D. 5.
11. (L.O.1.2)
c = (Q, Σ, δ, q0 , Q − F ) is a
minimal DFA for L.
A. (II), (III), (IV). B. (I), (II), (III). C. Only (I). D. (I), (II), (IV).
12. (L.O.1.2)
A. M1 ̸|= ϕ, M2 |̸ = ϕ, M3 |= ϕ. B. M1 |= ϕ, M2 |̸ = ϕ, M3 |̸ = ϕ.
C. M1 |̸ = ϕ, M2 |= ϕ, M3 |= ϕ. D. M1 |= ϕ, M2 |= ϕ, M3 |= ϕ.
A. All the other answers are incorrect. B. (a+b)*(b+a)* C. (abba)*
D. a*b*b*a*
A. The number of bit 1s of any string of L must be divisible by 3.

15. (L.O.1.3)

A. All other choices are correct. B. GCD(x, y) = GCD(x0 , y0 )

C. x ̸= 0 → GCD(y, y mod |x|) = GCD(x0 , y0 ) D. y ̸= 0 → GCD(x, x mod |y|) = GCD(x0 , y0 )
{ϕ} P {ψ}

{(a ≥ 1) ∧ (b ≥ 2)}
u = 0;
v = b;
{u = 0 ∧ v = b}
E
while ( v != Lb )
{
..
.P
}
{u = a · (b − v)}

(I) P := [u = u + a; v = v − 1; ] and Lb := 0
(II) P := [u = u + a; v = v − 2; ] and Lb := 1
(III) P := [u = u + a; v = v − 1; ] and Lb := 1
(IV) P := [u = u + a; v = v + 1; ] and Lb := 1.
statement?
⊢tot {ϕ} Prod {u = a · (b − 1)}?
A. (I) B. (IV) C. (II) D. (III)

17. (L.O.1.3)

A. ϕ = {a ∈ R, b ∈ Z}, ψ = {y = ab }. B. ϕ = {a ∈ R, b ∈ N}, ψ = {y = ab }.
C. ϕ = {a ∈ R, b ∈ Z+ }, ψ = {y = ab }. D. ϕ = {a ∈ R, b ∈ N}, ψ = {y = xz }.

A. All the other answers are incorrect. B. 1,2 C. 3,4 D. 1,3

A. If L1 is a regular language and the language L2 is not regular then L◦1 L2 is not regular.
D. For two languages L1 , L2 , we have L∗1 ◦ L∗2 ⊆ (L1 ∪ L2 )∗ .
A. Only (III) and (IV) B. Only (II), (III), and (IV)
C. Only (I), (II), and (IV) D. Only (II) and (III)

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . END OF EXAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Solution 1815
1. B. 6. B. 11. D. 16. D.
2. C. 7. B. 12. D. 17. D.
8. A. 13. B. 18. B.
3. B.
4. B. 9. D. 14. B. 19. D.
5. A. 10. D. 15. B. 20. B.


MIDTERM
Date 18/10/2023
A. (a+b)*(b+a)* B. All the other answers are incorrect. C. (abba)*
D. a*b*b*a*
{ϕ} P {ψ}

{(a ≥ 1) ∧ (b ≥ 2)}
u = 0;
v = b;
{u = 0 ∧ v = b}
E
while ( v != Lb )
{
..
.P
}
{u = a · (b − v)}

(I) P := [u = u + a; v = v − 1; ] and Lb := 0
(II) P := [u = u + a; v = v − 2; ] and Lb := 1
(III) P := [u = u + a; v = v − 1; ] and Lb := 1
(IV) P := [u = u + a; v = v + 1; ] and Lb := 1.
statement?
⊢tot {ϕ} Prod {u = a · (b − 1)}?
A. (IV) B. (I) C. (II) D. (III)
3. (L.O.1.3)
A. z ∈ Z ∧ yxz = ab . B. z ∈ Z ∧ y = xz . C. z ∈ N ∧ y = xz . D. z ∈ N ∧ yxz = ab .

4. (L.O.1.2)
A. M1 |= ϕ, M2 |̸ = ϕ, M3 |̸ = ϕ. B. M1 ̸|= ϕ, M2 |̸ = ϕ, M3 |= ϕ.
C. M1 |̸ = ϕ, M2 |= ϕ, M3 |= ϕ. D. M1 |= ϕ, M2 |= ϕ, M3 |= ϕ.

B. If L1 is a regular language and the language L2 is not regular then L◦1 L2 is not regular.

A. 1,2 B. All the other answers are incorrect. C. 3,4 D. 1,3

7. (L.O.1.3)

A. GCD(x, y) = GCD(x0 , y0 ) B. All other choices are correct.

C. x ̸= 0 → GCD(y, y mod |x|) = GCD(x0 , y0 ) D. y ̸= 0 → GCD(x, x mod |y|) = GCD(x0 , y0 )
8. (L.O.1.2)
c = (Q, Σ, δ, q0 , Q − F ) is a
minimal DFA for L.
A. (I), (II), (III). B. (II), (III), (IV). C. Only (I). D. (I), (II), (IV).

[|∀q(i < q ≤ n =⇒ a[i] ≤ a[q]) ∧ a[i] ≤ a[i − 1]|]
A. [|∀q(i − 1 < q ≤ n =⇒ a[i − 1] ≤ a[q])|] B. All the other answers are correct.
C. [|∀q(i < q ≤ n =⇒ a[i − 1] ≤ a[q])|] D. [|∀q(i ≤ q ≤ n =⇒ a[i] ≤ a[q])|]
B. The number of bit 1s of any string of L must be divisible by 3.
11. (L.O.1.3)

should use?
(i−1)/2 i/2
X X
A. s = 2k ∧ (i ≤ n + 1). B. s = 2k ∧ (i ≤ n + 1).
k=0 k=0
(i−1)/2 i/2
X X
C. s = 2k. D. s = 2k ∧ (i ≤ n).
k=0 k=0




A. (IV) B. (I) C. (II) D. (III)
A. L = {w ∈ Σ∗ | w contains exactly two 2′ s}. B. L = {w ∈ Σ∗ | w contains at least two 2’s consecutively}.

C. L = {w ∈ Σ∗ | w contains at most two 2′ s}. D. L = {w ∈ Σ∗ | w contains at least two 2′ s}.
14. (L.O.1.3)

A. ϕ = {a ∈ R, b ∈ N}, ψ = {y = ab }. B. ϕ = {a ∈ R, b ∈ Z}, ψ = {y = ab }.
C. ϕ = {a ∈ R, b ∈ Z+ }, ψ = {y = ab }. D. ϕ = {a ∈ R, b ∈ N}, ψ = {y = xz }.

15. (L.O.3.2)
a a
A B C a
b b
a
a E b
b
a b
b D G a F
b
A. 4. B. 7. C. 6. D. 5.
16. (L.O.2.3) Let L be the language consisting of string w ∈ {0, 1}∗
that the number of occurrences of sub-string
A. Only (II), (III), and (IV) B. Only (III) and (IV)
C. Only (I), (II), and (IV) D. Only (II) and (III)
max=0;
if(max<a) max=a;
if(max<b) max=b;
if(max<c) max=c;
A. ϕ : a, b, c >= 0, ψ : a 0, ψ : a, b, c ≤ max D. ϕ : a, b, c >= 0, ψ : a, b, c ≤ max
r = u∗ = (bc)∗ and s = v ∗ = (cb)∗ .
A. (III) B. (I) C. (II) D. (IV)

expressions?
A. IV B. I C. II D. III

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . END OF EXAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Solution 1816
1. A. 7. A. 13. A. 18. B.
2. D. 8. D. 14. D.
3. D. 9. B. 19. A.
15. D.
4. D. 10. A. 20. C.
5. D. 11. A. 16. A.
6. A. 12. A. 17. A.


MIDTERM
Date 18/10/2023
1. (L.O.1.3)

should use?
(i−1)/2 (i−1)/2
X X
A. s = 2k ∧ (i ≤ n + 1). B. s = 2k.
k=0 k=0
i/2 i/2
X X
C. s = 2k ∧ (i ≤ n + 1). D. s = 2k ∧ (i ≤ n).
k=0 k=0



A. (IV) B. (II) C. (I) D. (III)

3. (L.O.3.2)
a a
A B C a
b b
a
a E b
b
a b
b D G a F
b
A. 4. B. 6. C. 7. D. 5.
A. (a+b)*(b+a)* B. (abba)* C. All the other answers are incorrect.
D. a*b*b*a*
5. (L.O.1.3)

A. GCD(x, y) = GCD(x0 , y0 ) B. x ̸= 0 → GCD(y, y mod |x|) = GCD(x0 , y0 )

C. All other choices are correct. ̸ 0 → GCD(x, x mod |y|) = GCD(x0 , y0 )
D. y =
A. L = {w ∈ Σ∗ | w contains exactly two 2′ s}. B. L = {w ∈ Σ∗ | w contains at most two 2′ s}.

∗
C. L = {w ∈ Σ | w contains at least two 2’s consecutively}.
D. L = {w ∈ Σ∗ | w contains at least two 2′ s}.
7. (L.O.1.3)
A. z ∈ Z ∧ yxz = ab . B. z ∈ N ∧ y = xz . C. z ∈ Z ∧ y = xz . D. z ∈ N ∧ yxz = ab .

A. Only (II), (III), and (IV) B. Only (I), (II), and (IV)
C. Only (III) and (IV) D. Only (II) and (III)
B. The number of bit 1s and the number of bit 0s of any string of L must be the same.
C. All other choices are incorrect.
10. (L.O.1.3)

A. ϕ = {a ∈ R, b ∈ N}, ψ = {y = ab }. B. ϕ = {a ∈ R, b ∈ Z+ }, ψ = {y = ab }.
C. ϕ = {a ∈ R, b ∈ Z}, ψ = {y = ab }. D. ϕ = {a ∈ R, b ∈ N}, ψ = {y = xz }.

[|∀q(i < q ≤ n =⇒ a[i] ≤ a[q]) ∧ a[i] ≤ a[i − 1]|]
A. [|∀q(i − 1 < q ≤ n =⇒ a[i − 1] ≤ a[q])|] B. [|∀q(i < q ≤ n =⇒ a[i − 1] ≤ a[q])|]
C. All the other answers are correct. D. [|∀q(i ≤ q ≤ n =⇒ a[i] ≤ a[q])|]
B. The number of states of a DFA recognizing only L must be divisible by 3.
C. The number of bit 1s of any string of L must be divisible by 3.

max=0;
if(max<a) max=a;
if(max<b) max=b;
if(max<c) max=c;
A. ϕ : a, b, c >= 0, ψ : a 0, ψ : a, b, c ≤ max

C. ϕ : T , ψ : a, b, c ≤ max D. ϕ : a, b, c >= 0, ψ : a, b, c ≤ max
r = u∗ = (bc)∗ and s = v ∗ = (cb)∗ .

A. (III) B. (II) C. (I) D. (IV)
expressions?
A. IV B. II C. I D. III

B. If L1 , L2 , are finite languages then |L1 ◦ L2 | = |L1 | · |L2 |.
C. If L1 is a regular language and the language L2 is not regular then L◦1 L2 is not regular.
{ϕ} P {ψ}

{(a ≥ 1) ∧ (b ≥ 2)}
u = 0;
v = b;
{u = 0 ∧ v = b}
E
while ( v != Lb )
{
..
.P
}
{u = a · (b − v)}

(I) P := [u = u + a; v = v − 1; ] and Lb := 0
(II) P := [u = u + a; v = v − 2; ] and Lb := 1
(III) P := [u = u + a; v = v − 1; ] and Lb := 1
(IV) P := [u = u + a; v = v + 1; ] and Lb := 1.
statement?
⊢tot {ϕ} Prod {u = a · (b − 1)}?
A. (IV) B. (II) C. (I) D. (III)
18. (L.O.1.2)
A. M1 |= ϕ, M2 |̸ = ϕ, M3 |̸ = ϕ. B. M1 ̸|= ϕ, M2 |= ϕ, M3 |= ϕ.
C. M1 |̸ = ϕ, M2 |̸ = ϕ, M3 |= ϕ. D. M1 |= ϕ, M2 |= ϕ, M3 |= ϕ.

19. (L.O.1.2)
c = (Q, Σ, δ, q0 , Q − F ) is a
minimal DFA for L.
A. (I), (II), (III). B. Only (I). C. (II), (III), (IV). D. (I), (II), (IV).

A. 1,2 B. 3,4 C. All the other answers are incorrect. D. 1,3
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . END OF EXAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Solution 1817
1. A. 7. D. 13. C. 17. D.
2. A. 8. A.
18. D.
3. D. 9. A. 14. A.
4. A. 10. D. 15. B. 19. D.
5. A. 11. C.
6. A. 12. A. 16. D. 20. A.


MIDTERM
Date 18/10/2023
A. a*b*b*a* B. (a+b)*(b+a)* C. (abba)*



A. (III) B. (IV) C. (II) D. (I)

3. (L.O.1.3)

should use?
i/2 (i−1)/2
X X
A. s = 2k ∧ (i ≤ n). B. s = 2k ∧ (i ≤ n + 1).
k=0 k=0
(i−1)/2 i/2
X X
C. s = 2k. D. s = 2k ∧ (i ≤ n + 1).
k=0 k=0
4. (L.O.3.2)
a a
A B C a
b b
a
a E b
b
a b
b D G a F
b
A. 5. B. 4. C. 6. D. 7.

{ϕ} P {ψ}

{(a ≥ 1) ∧ (b ≥ 2)}
u = 0;
v = b;
{u = 0 ∧ v = b}
E
while ( v != Lb )
{
..
.P
}
{u = a · (b − v)}

(I) P := [u = u + a; v = v − 1; ] and Lb := 0
(II) P := [u = u + a; v = v − 2; ] and Lb := 1
(III) P := [u = u + a; v = v − 1; ] and Lb := 1
(IV) P := [u = u + a; v = v + 1; ] and Lb := 1.
statement?
⊢tot {ϕ} Prod {u = a · (b − 1)}?
A. (III) B. (IV) C. (II) D. (I)
6. (L.O.1.3)

A. ϕ = {a ∈ R, b ∈ N}, ψ = {y = xz }. B. ϕ = {a ∈ R, b ∈ N}, ψ = {y = ab }.
C. ϕ = {a ∈ R, b ∈ Z+ }, ψ = {y = ab }. D. ϕ = {a ∈ R, b ∈ Z}, ψ = {y = ab }.

7. (L.O.1.2)
c = (Q, Σ, δ, q0 , Q − F ) is a
minimal DFA for L.
A. (I), (II), (IV). B. (I), (II), (III). C. Only (I). D. (II), (III), (IV).
8. (L.O.1.3)
A. z ∈ N ∧ yxz = ab . B. z ∈ Z ∧ yxz = ab . C. z ∈ N ∧ y = xz . D. z ∈ Z ∧ y = xz .
A. Only (II) and (III) B. Only (II), (III), and (IV)
C. Only (I), (II), and (IV) D. Only (III) and (IV)

max=0;
if(max<a) max=a;
if(max<b) max=b;
if(max<c) max=c;
A. ϕ : a, b, c >= 0, ψ : a, b, c ≤ max B. ϕ : a, b, c >= 0, ψ : a 0, ψ : a, b, c ≤ max D. ϕ : T , ψ : a, b, c ≤ max
A. L is not a regular language.
r = u∗ = (bc)∗ and s = v ∗ = (cb)∗ .
A. (IV) B. (III) C. (II) D. (I)
expressions?
A. III B. IV C. II D. I

A. For two languages L1 , L2 , we have L∗1 ◦ L∗2 ⊆ (L1 ∪ L2 )∗ .

15. (L.O.1.2)
A. M1 |= ϕ, M2 |= ϕ, M3 |= ϕ. B. M1 |= ϕ, M2 |̸ = ϕ, M3 |̸ = ϕ.
C. M1 |̸ = ϕ, M2 |= ϕ, M3 |= ϕ. D. M1 |̸ = ϕ, M2 |̸ = ϕ, M3 |= ϕ.

A. 1,3 B. 1,2 C. 3,4
[|∀q(i < q ≤ n =⇒ a[i] ≤ a[q]) ∧ a[i] ≤ a[i − 1]|]
A. [|∀q(i ≤ q ≤ n =⇒ a[i] ≤ a[q])|] B. [|∀q(i − 1 < q ≤ n =⇒ a[i − 1] ≤ a[q])|]
C. [|∀q(i < q ≤ n =⇒ a[i − 1] ≤ a[q])|] D. All the other answers are correct.
A. L = {w ∈ Σ∗ | w contains at least two 2′ s}. B. L = {w ∈ Σ∗ | w contains exactly two 2′ s}.

C. L = {w ∈ Σ∗ | w contains at most two 2′ s}. D. L = {w ∈ Σ∗ | w contains at least two 2’s consecutively}.

19. (L.O.1.3)

A. y ̸= 0 → GCD(x, x mod |y|) = GCD(x0 , y0 ) B. GCD(x, y) = GCD(x0 , y0 )

C. x ≠ 0 → GCD(y, y mod |x|) = GCD(x0 , y0 ) D. All other choices are correct.
A. L is not a regular language.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . END OF EXAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Solution 1818
1. B. 7. A. 12. B. 17. D.
2. B. 8. A. 13. C.
18. B.
3. B. 9. B.
4. A. 14. A.
10. D. 19. B.
5. A. 15. A.
11. B.
6. A. 16. B. 20. B.

Midterm MM Co2011 Hk231 en Da

Uploaded by

Copyright:

Available Formats

Midterm MM Co2011 Hk231 en Da

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Midterm MM Co2011 Hk231 en Da

Uploaded by

Copyright:

Available Formats

Lecturer: October 2nd, 2023 Approved by: October 2nd, 2023

(Signature and Fullname) (Signature and Fullname)

Semester/Academic year 1 2023-2024

2. (L.O.1.3) Given a program finding max for 3 integers a,b,c:

A. ϕ : a, b, c >= 0, ψ : a < b < c < max B. ϕ : a, b, c >= 0, ψ : a, b, c ≤ max

Stu.ID: .......................................... Stu.Fullname: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Code: 1811 Page: 1/6

where pre-conditions ϕ := (a ≥ 1) ∧ (b ≥ 2) and post-conditions ψ should be suitably defined. A variant K

In the following options of core program P and lower bound Lb:

A. (IV) B. (III) C. (II) D. (I)

Stu.ID: .......................................... Stu.Fullname: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Code: 1811 Page: 2/6

Which of the following couples are the same?

6. (L.O.1.3) Given a post-condition for a correct program:

Stu.ID: .......................................... Stu.Fullname: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Code: 1811 Page: 3/6

Given the following program, with ⊤ as a precondi-

Stu.ID: .......................................... Stu.Fullname: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Code: 1811 Page: 4/6

A. (III) B. (IV) C. (II) D. (I)

(I) r + s; (II) r + s + c r + b s; (III) r + s + b r + c s; (IV) s + r.

• Girl(a) = “a is a girl”, Boy(b) = “b is a boy”,

• SportP rize(x) = “x is a prize in Sport tournament”,

• M athP rize(y) = “y is a prize in Mathematics competition”,

• Sibling(a, b) = “a and b are siblings in a family”,

• W inSport(w, s) = “w won a sport prize s”,

• W inM ath(u, m) = “u won a mathematics prize m”.

Which of the following options best represents the given statement?

(I) ∀x [SportP rize(x) −→ ∃y (Girl(y) ∧ W inSport(y, x))]

(II) [ (∃f, Girl(f ) ∧ ∀x, SportP rize(x)) −→ W inSport(f, x) ]

(III) ∃f [ (Girl(f ) ∧ ∀x, SportP rize(x)) −→ W inSport(f, x) ]

(IV) ∃f [ (Girl(f ) ∧ ∀x, SportP rize(x)) −→ W inSport(f, x) ]

A. (IV) B. (III) C. (II) D. (I)

In the following program, % is the division with

A. GCD(x, y) = GCD(x0 , y0 ) B. y ̸= 0 → GCD(x, x mod |y|) = GCD(x0 , y0 )

Stu.ID: .......................................... Stu.Fullname: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Code: 1811 Page: 5/6

Consider program P below. (Weakest) precondition ϕ

A. L = {w ∈ Σ∗ | w contains exactly two 2′ s}. B. L = {w ∈ Σ∗ | w contains at least two 2′ s}.

Stu.ID: .......................................... Stu.Fullname: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Code: 1811 Page: 6/6

6. D. 11. B. 15. A. 20. A.

Stu.ID: .......................................... Stu.Fullname: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Code: 1811 Page: 1/6

Semester/Academic year 1 2023-2024

Given the following program, with ⊤ as a precondi-

Stu.ID: .......................................... Stu.Fullname: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Code: 1812 Page: 1/6

where pre-conditions ϕ := (a ≥ 1) ∧ (b ≥ 2) and post-conditions ψ should be suitably defined. A variant K

In the following options of core program P and lower bound Lb:

A. (I) B. (IV) C. (III) D. (II)

4. (L.O.1.3) Given a post-condition for a correct program:

6. (L.O.1.3) Given a program finding max for 3 integers a,b,c:

A. ϕ : T , ψ : a, b, c ≤ max B. ϕ : a, b, c >= 0, ψ : a < b < c < max

Stu.ID: .......................................... Stu.Fullname: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Code: 1812 Page: 2/6

• Girl(a) = “a is a girl”, Boy(b) = “b is a boy”,

• SportP rize(x) = “x is a prize in Sport tournament”,

• M athP rize(y) = “y is a prize in Mathematics competition”,

• Sibling(a, b) = “a and b are siblings in a family”,

• W inSport(w, s) = “w won a sport prize s”,

• W inM ath(u, m) = “u won a mathematics prize m”.

Which of the following options best represents the given statement?

(I) ∀x [SportP rize(x) −→ ∃y (Girl(y) ∧ W inSport(y, x))]

(II) [ (∃f, Girl(f ) ∧ ∀x, SportP rize(x)) −→ W inSport(f, x) ]

(III) ∃f [ (Girl(f ) ∧ ∀x, SportP rize(x)) −→ W inSport(f, x) ]

(IV) ∃f [ (Girl(f ) ∧ ∀x, SportP rize(x)) −→ W inSport(f, x) ]

A. (I) B. (IV) C. (III) D. (II)