Academic year 2007/08 - Course on Concurrency: 2^{nd} partial examination

You may consult the slides of the lectures. No other document or electronic device is allowed. Answers should be formulated in French or English, and preferably in a rigorous and sharp style.

Please write the solutions to the two parts in separate sheets.

First part

Exercise 1 (Expressivity, 6.5 points) Recall that the language generated by P, L(P), is the set of all sequences generated from the finite-maximal labelled transitions of P. I.e., L(P) = {s | ∃Q : P ⟹^{s} Q ∧ ∀α : Q −̸→^{α}}.

• Give a CCS! (CCS with replication) process P that generates the nonregular language {a^{n}b^{n}c | n ≥ 0}.

Now recall that P is weakly terminating iff P generates at least one sequence, i.e., L(P) ≠ ∅. Also recall that P is termination-preserving iff whenever P ⟹^{s} Q ⟶^{τ} R: If Q is weakly terminating then R is weakly terminating.

• Prove that termination-preserving CCS! processes can generate non context-free languages. Hint: Since context-free languages are closed under intersection with regular languages, it suffices to give a P such that L(P) ∩ a^{∗}b^{∗}c^{∗} = {a^{n}b^{n}c^{n} | n ≥ 0}.

Exercise 2 (Probability, 4.5 points) Consider the following process P:

(νa)(νb)((a.b.c.0 + τ.0) | (let X = (ā.X ⊕_{1/2} b̄.0) in X))

Assume that a, b and c are pairwise different.

• Draw the graph of P.

• How may different schedulers we have for P? Motivate your answer.

• What is the probability that c will be executed, under the different schedulers?

0.1 Solution second exercise