Observations

1. Is the language consisting of strings like “a”, “ab”, “aba”, “abab”, and so on, a regular language? Explain, why. If yes, the best answer would be to write a regex; you can also just describe the grammar. If not, just explain why.

2. A language is defined in BNF; determine the complexity of the machine you need to parse it: Finite State Machine, Stack Machine, Turing Machine, and explain your decision.
a)
<x> ::= (<y>+<z>)
<y> := a<y>
<y> := b<z>
<z> := c
<z> := d

b)
<x> ::= a<x>b<x>c
<x> ::= d

3. Given two binary relationship R: A<->B and S: B<->C, describe their composition, where
A = {all integers}, B = {all real numbers}, C = {all positive integer numbers}, aRb = (b == log2(a)), bSc = (b == c).

4. In the following example of using Δ schema in Z notation, explain the constraints:
AddBirthday ≘ [
Δ BirthdayBook;
name? : NAME;
date? : DATE;
|
name? ∉ known;
birthday′ = birthday ∪ {name? ↦ date?}
]

5. You already wrote the ping-pong game in pi-calculus, with two players. Now imagine there are 4 players, 2 on each side, A1,A2,B1,B2, and a couch that sends the signal to A1 which serves the ball (sends Ping); then one of B1 or B2 gets the Ping, and sends back a Pong; either A1 or A2 gets the Pong, and sends back a Ping. The game never stops. Write this scenario in pi-calculus.

Just wrote slides

comments? (you can do them right in the document)