### Indice

### 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^{n} denote the nth power of 7. Prove by induction that for any natural number n > 1 we have that 3 divides 7^{n} - 1.

#### Exercise 4

Consider the strings (i.e., finite sequences) of symbols {0,1}. Let #_{0}(s) and #_{1}(s) denote the number of occurrences of 0 and 1 in the string s, respectively, and let s^{n} 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 #
_{1}(s) is odd. - The set of all and only strings s such that #
_{0}(s) = #_{1}(s). - The set of all and only strings s such that s = (01)
^{n}for some natural number n. - The set of all and only strings s such that s = 0
^{n}1^{n}for some natural number n.

#### Exercise 5

Let us consider the imperative code fragment

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

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