==== Preliminary test for the course on Models of Computation ====

There are no prerequisites for MOD, but we expect the students to have some familiarity with discrete mathematics, first-order logic formulas, context-free grammars, and code fragments in imperative and functional style.

We encourage the students to use the following basic exercises to self-assess their level of knowledge for the above arguments. 

=== Exercise 1 ===

Write the formal definitions of //injective// function and //surjective// function. Prove that the composition of two injective functions (respectively of two surjective functions) is an injective function (respectively, a surjective function).

=== Exercise 2 ===

Are the formulas "(∀x. P(x)) ⇒ Q" and "∀x. (P(x) ⇒ Q)" equivalent?

=== Exercise 3 ===

Let 7<sup>n</sup> denote the nth power of 7. Prove by induction that for any natural number n > 1 we have that 3 divides 7<sup>n</sup> - 1.

=== Exercise 4 ===

Consider the strings (i.e., finite sequences) of symbols {0,1}. Let #<sub>0</sub>(s) and #<sub>1</sub>(s) denote the number of occurrences of 0 and 1 in the string s, respectively, and let s<sup>n</sup> denote the sequence obtained as the concatenation of n instances of the string s.  Define context-free grammars that generate each of the following languages
  - The set of all and only strings s such that #<sub>1</sub>(s) is odd.
  - The set of all and only strings s such that #<sub>0</sub>(s) = #<sub>1</sub>(s).
  - The set of all and only strings s such that s = (01)<sup>n</sup> for some natural number n.
  - The set of all and only strings s such that s = 0<sup>n</sup> 1<sup>n</sup> for some natural number n.

=== Exercise 5 ===

Let us consider the imperative code fragment

<code>while (x!=0 and y!=0) do { 
    x := x-y; 
    y := y-1 
}</code>

where x and y are two integer variables. 
For which initial values of x and y does the execution of the above program terminate?