DidaWiki

There are no prerequisistes 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.

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).

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

Let 2^n denote the nth power of 2. Prove by induction that for any natural number n > 1 we have that 3 divides 2^n - 1.

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

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 = 0^n 1^n for some natural number n.

Let us consider the program

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

For which initial values of x and y does the execution of the above program terminate?