
\documentclass[11pt]{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*{Concurrency:  Solutions forExercise 1 from the first part of the $2^{\w{nd}}$ partial examination}

%\subsection*{First part}
\begin{exercise}[Expressivity, 11 minutes]

Recall that CCS! denotes CCS with the replication or bang process $!P$. Given a CCS! process $P$, recall that the language generated by $P$, $L(P),$ is the set of all finite maximal sequences generated from the labeled 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!.

\begin{itemize} 
\item Question: The  
 regular set  \[ \{ a^n \ | \  n\geq 0 \}\]  
 is generated by one of the following of processes. Which one?
 
\begin{enumerate}
 \item  The process $!(a.0)$
 \item   The process $(\nu u)( \out{u}.0 \ | \  !(u.a.\out{u}.0) \  | \  u.0)$
 \item The process $(\nu u)(\out{u}.0 \ | \  !(u.a.0) \ \ \  | \  u.0)$
\end{enumerate}
\end{itemize}
\end{exercise}

\newpage

\begin{exercise}[Probability, 7 minutes]
Consider the following process  $P$:
\[
a.(b.0 \oplus_{1/2} c.0) + a.(\tau.b.0 + \tau.c.0)
\]
Assume that $a$, $b$ and $c$ are pairwise different. 
$P$ gives rise to the following transition graph:

\vspace{9cm}
\end{exercise}


\begin{itemize}
\item How may different schedulers we have for $P$? 
\item What is the probability that $b$ will be executed, under the different schedulers?
\end{itemize}
\end{document}


\subsubsection*{Solution}
\begin{itemize}
\item 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}

\item
The probability of performing $b$ is
\begin{itemize}
\item $1/2$ under $\sigma_1$,
\item $1$ under $\sigma_2$, 
\item $0$ under $\sigma_3$.
\end{itemize}
\end{itemize}


\end{document}

