# DidaWiki

### Strumenti Sito

magistraleinformatica:mod:start:pretest

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

1. The set of all and only strings s such that #1(s) is odd.
2. The set of all and only strings s such that #0(s) = #1(s).
3. The set of all and only strings s such that s = (01)n for some natural number n.
4. The set of all and only strings s such that s = 0n 1n 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?

magistraleinformatica/mod/start/pretest.txt · Ultima modifica: 01/03/2016 alle 23:11 (4 anni fa) da Roberto Bruni

### Strumenti Pagina 