
\documentclass[11pt,a4]{article}

\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{exercise}[theorem]{Exercise}
\newcommand{\cl}[1]{{\cal #1}}          % \cl{R} to make R calligraphic
\newcommand{\arrow}{\rightarrow}        % right thin arrow
\newcommand{\infer}[2]{\begin{array}{c} #1 \\ \hline #2 \end{array}}
                                        % to make a centered inference rule
\newcommand{\set}[1]{\{#1\}}            % set enumeration
\newcommand{\xst}[2]{\exists\, #1\;\: #2}
\newcommand{\act}[1]{\stackrel{#1}{\rightarrow}} %labelled action low high
\newcommand{\wact}[1]{\stackrel{#1}{\Rightarrow}} %weak labelled action low %high
\newcommand{\w}[1]{\it #1}
\newcommand{\wbis}{\approx}

%%% Reductions
\newcommand{\lred}[1]{\stackrel{\,\,#1\,\,}{\longrightarrow}} 
\newcommand{\Lred}[1]{\stackrel{\,\,#1\,\,}{\Longrightarrow}} 

\newcommand{\os}{[\![}
\newcommand{\cs}{]\!]}

\newcommand{\out}[1]{\overline{#1}}




\begin{document}

\section*{Academic year 2007/08 - Course on Concurrency: $2^{\w{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.

\subsection*{First part}
\begin{exercise}[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$. More precisely, \[ L(P)=\{ s \in \mathcal{L}^* \ | \  \exists Q: P\Lred{s}Q \wedge \forall \alpha \in \mathcal{L}\cup\{\tau\}: Q\not\lred{\alpha} \}.\] 
 where $\mathcal{L}$ denote the set of visible actions in CCS.

 \end{exercise}
 
\begin{itemize}
 \item {\bf Exercise 1.1:} Give a CCS!  (CCS with replication) process $P$ that generates the non-regular language $\{ a^nb^nc \ | \ n\geq 0 \}.$
 \item {\bf A Solution: } Consider the process $P$ below:
\begin{eqnarray}
P& = & (\nu k_1,k_2,k_3,  u_b)
{( \
\out{k_1} \ | \  \out{k_2} \ | \  Q_a  \ | \   Q_b  \ | \   Q_c )} \nonumber \\
Q_a & = & !k_1.a.(\out{k_1}  \ | \   \out{k_3}  \ | \   \out{u_b} ) \nonumber\\
Q_b & = & k_1. !k_3.k_2.u_b.b.\out{k_2}  \nonumber \\
Q_c & = & k_2.(c  \ | \  u_b.DIV ) \nonumber
\end{eqnarray}
 where $DIV=!\tau.$ One can verify  that $L(P)=\{ a^{n} b^{n} c  \}$.  
 
\end{itemize}

Now recall that $P$ is \emph{weakly terminating}  iff  $P$ generates at least one sequence, i.e., $L(P)\neq\emptyset$.  Also recall that  $P$ is   \emph{termina\-tion-preserving}   iff whenever $P \Lred{s} Q \lred{\tau} R$: If $Q$ is weakly terminating  then $R$ is weakly terminating.

\begin{itemize}
 \item {\bf Exercise 1.2:} 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)\cap a^*b^*c^* = \{ a^nb^nc^n \ | \ n\geq 0 \}$.
  \item {\bf A Solution:} Take  
$$P= (\nu k, u){(\out{k}  \ | \  !k.a.(\out{k}  \ | \  \out{u}))  \ | \ k . !u.(b  \ | \  c))}$$  

One can verify that $P$ is termination-preserving. Furthermore,  $L(P) \cap a^*b^*c^* = a^n b^n c^n$, hence $L(P)$ is not a CFL since CFL's are closed under intersection with regular languages.
  
\end{itemize}
 


\newpage
\begin{exercise}[Probability, 4.5 points]
Consider the following process  $P$:
\[
(\nu a) (\nu b) ((a.b.c.0 + \tau.0) \mid (\mbox{\bf let } X = (\bar{a}.X \oplus_{1/2} \bar{b}.0)\; \mbox{\bf in } X))
\]
Assume that $a$, $b$ and $c$ are pairwise different. 
\end{exercise}

\begin{description}
\item[Exercise 2.1] Draw the graph of $P$. 
\subsubsection*{Solution}
Let $P_1$ be the process $ a.b.c.0 + \tau.0$ and $P_2 $ be the process $ \mbox{\bf let } X = (\bar{a}.X \oplus_{1/2} \bar{b}.0)\; \mbox{\bf in } X$. The graph generated by $P$ is the following: 

\newpage
\item[Exercise 2.2] How may different schedulers we have for $P$? Motivate your answer.
\subsubsection*{Solution}
There are 3 different schedulers:
 \begin{itemize}
 \item The scheduler $\sigma_1$, which selects the transition {\bf I},
 \item  the scheduler $\sigma_2$, which selects the transition {\bf II} and then {\bf III},
\item the scheduler $\sigma_3$, which selects the transition {\bf II} and then {\bf IV}.
\end{itemize}
\vspace{1cm}

\item[Exercise 2.3] What is the probability that $c$ will be executed, under the different schedulers?
\subsubsection*{Solution}
The probability of performing $c$ is
\begin{itemize}
\item $0$ under $\sigma_1$,
\item $1/4$ under $\sigma_2$, 
\item $0$ under $\sigma_3$.
\end{itemize}
\end{description}


\end{document}

