\documentclass[12pt,a4paper]{article}

\usepackage{amstext}
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage[latin1]{inputenc}
\usepackage{cancel}
\usepackage{fancyhdr}
\usepackage{listings}
\usepackage{gastex}
\usepackage{pstricks}
\usepackage{pst-node}
%\usepackage{ngerman}

\title{\textsc{Embedded Systems \\ \large Assignment 2}}
\author{\shortstack[c]{Jan Hendrik Dithmar\\ \scriptsize 2031259} \and \shortstack[c]{Pascal Gwosdek\\ \scriptsize 2505221}}
\date{}

\pagestyle{fancy}

\lhead{Assignment 2}
\chead{}
\rhead{Dithmar (2031259), Gwosdek (2505221)}
\lfoot{Embedded Systems}
\cfoot{Page \thepage}
\rfoot{SS 2007}

\begin{document}

\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

\newcommand{\exercise}[1]{\subsection{#1}}
\renewcommand{\theenumi}{\textbf{\alph{enumi}}}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetC}{\ensuremath{\mathbb{C}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\bild}[2]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[width=#1cm]{#2}\\[0.2cm]
	\end{figure}
	}

\newcommand{\m}[1]{\begin{pmatrix}#1\end{pmatrix}}
\newcommand{\+}{\phantom{-}}
\newcommand{\f}{\frac}

\maketitle

\thispagestyle{empty}

\newpage
\setcounter{page}{1}
\setcounter{section}{2}

\exercise{Statecharts}
\begin{enumerate}
%(a)
\item \
\begin{center}
\begin{pspicture}(0,0)(14,15)
\psframe(0,2)(14,15)
\rput(7,13){\rnode{whiterunning}{\psframebox{running white}}}
\rput(7,11){\rnode{whitepausing}{\psframebox{pausing white}}}
\pcline{**->}(6.5,13.7)(7,13.3)
\pcline{->}(6.2,11.3)(6.2,12.7)\Aput{\tiny black\_moves}
\pcline{->}(6.7,12.7)(6.7,11.3)\Aput{\tiny tick [white = 0] / black\_wins}
\pcline{<-}(8.4,11)(10.6,11)
\pcline(10.6,11)(10.6,12.8)
\rput(12.1,12.2){\tiny white\_moves [wm $=$ 0] /}
\rput(12.3,11.8){\tiny wm := 20, white := 3600}
\pcline(10.6,12.8)(8.4,12.8)
\pcline{->}(4.3,11)(5.6,11)
\pcline(4.3,11)(4.3,12.8)
\rput(2.8,12.2){\tiny white\_moves [wm $\neq$ 0] /}
\rput(3.2,11.8){\tiny wm := wm - 1}
\pcline(4.3,12.8)(5.6,12.8)
\ncloop[angleB=180]{->}{whiterunning}{whiterunning}\Bput{\tiny tick [white $>$ 0] / white := white - 1}
\psline[linestyle=dashed](0,10)(14,10)
\rput(7,8){\rnode{blackrunning}{\psframebox{running black}}}
\rput(7,6){\rnode{blackpausing}{\psframebox{pausing black}}}
\pcline{**->}(6.5,5.2)(7,5.7)
\pcline{->}(6.2,6.3)(6.2,7.7)\Aput{\tiny white\_moves}
\pcline{->}(6.7,7.7)(6.7,6.3)\Aput{\tiny tick [black = 0] / white\_wins}
\pcline{<-}(8.4,6)(10.6,6)
\pcline(10.6,6)(10.6,7.8)
\rput(12.1,7.2){\tiny black\_moves [bm $=$ 0] /}
\rput(12.3,6.8){\tiny bm := 20, black := 3600}
\pcline(10.6,7.8)(8.4,7.8)
\pcline{->}(4.3,6)(5.6,6)
\pcline(4.3,6)(4.3,7.8)
\rput(2.8,7.2){\tiny black\_moves [bm $\neq$ 0] /}
\rput(3.2,6.8){\tiny bm := bm - 1}
\pcline(4.3,7.8)(5.6,7.8)
\ncloop[angleB=180]{->}{blackrunning}{blackrunning}\Bput{\tiny tick [black $>$ 0] / black := black - 1}
\psline[linestyle=dashed](0,5)(14,5)
\rput(7,3){\rnode{timer}{\psshadowbox{1 sec}}}
\ncloop[angleB=180,loopsize=1]{->}{timer}{timer}\Bput{\tiny timeout/tick}
\rput(7,0){\rnode{off}{\psframebox{off}}}
\pcline{->}(6.8,0.3)(4,2)
\rput(3.0,1.1){\tiny key\_on / white := 7200, black := 7200, }
\rput(4.5,0.7){\tiny wm := 40, bm := 40}
\pcline{->}(10,2)(7.2,0.3)\Aput{\tiny key\_off}
\end{pspicture}
\end{center}
%(b)
\newpage
\item \
\begin{center}
\begin{pspicture}(0,0)(14,15)
\psframe(0,2)(14,15)
\rput(7,13){\rnode{whiterunning}{\psframebox{running white}}}
\rput(7,11){\rnode{whitepausing}{\psframebox{pausing white}}}
\pcline{**->}(6.5,13.7)(7,13.3)
\pcline{->}(6.2,11.3)(6.2,12.7)\Aput{\tiny black\_moves}
\pcline{->}(6.7,12.7)(6.7,11.3)\Aput{\tiny tick [white = 0] / black\_wins}
\pcline{<-}(8.4,11)(10.6,11)
\pcline(10.6,11)(10.6,12.8)
\rput(12.1,12.2){\tiny white\_moves [wm $=$ 0] /}
\rput(12.3,11.8){\tiny wm := -1, white := 3600}
\pcline(10.6,12.8)(8.4,12.8)
\pcline{->}(4.3,11)(5.6,11)
\pcline(4.3,11)(4.3,12.8)
\rput(2.8,12.2){\tiny white\_moves [wm $\neq$ 0] /}
\rput(3.2,11.8){\tiny wm := wm - 1}
\pcline(4.3,12.8)(5.6,12.8)
\ncloop[angleB=180]{->}{whiterunning}{whiterunning}\Bput{\tiny tick [white $>$ 0] / white := white - 1}
\psline[linestyle=dashed](0,10)(14,10)
\rput(7,8){\rnode{blackrunning}{\psframebox{running black}}}
\rput(7,6){\rnode{blackpausing}{\psframebox{pausing black}}}
\pcline{**->}(6.5,5.2)(7,5.7)
\pcline{->}(6.2,6.3)(6.2,7.7)\Aput{\tiny white\_moves}
\pcline{->}(6.7,7.7)(6.7,6.3)\Aput{\tiny tick [black = 0] / white\_wins}
\pcline{<-}(8.4,6)(10.6,6)
\pcline(10.6,6)(10.6,7.8)
\rput(12.1,7.2){\tiny black\_moves [bm $=$ 0] /}
\rput(12.3,6.8){\tiny bm := -1, black := 3600}
\pcline(10.6,7.8)(8.4,7.8)
\pcline{->}(4.3,6)(5.6,6)
\pcline(4.3,6)(4.3,7.8)
\rput(2.8,7.2){\tiny black\_moves [bm $\neq$ 0] /}
\rput(3.2,6.8){\tiny bm := bm - 1}
\pcline(4.3,7.8)(5.6,7.8)
\ncloop[angleB=180]{->}{blackrunning}{blackrunning}\Bput{\tiny tick [black $>$ 0] / black := black - 1}
\psline[linestyle=dashed](0,5)(14,5)
\rput(7,3){\rnode{timer}{\psshadowbox{1 sec}}}
\ncloop[angleB=180,loopsize=1]{->}{timer}{timer}\Bput{\tiny timeout/tick}
\rput(7,0){\rnode{off}{\psframebox{off}}}
\pcline{->}(6.8,0.3)(4,2)
\rput(3.0,1.1){\tiny key\_on / white := 7200, black := 7200, }
\rput(4.5,0.7){\tiny wm := 40, bm := 40}
\pcline{->}(10,2)(7.2,0.3)\Aput{\tiny key\_off}
\end{pspicture}
\end{center}
%(c)
\newpage
\item \
\begin{center}
\begin{pspicture}(0,0)(12,15)
\psframe(0,2)(12,15)
\rput(4,13){\rnode{whiterunning}{\psframebox{running white}}}
\rput(4,11){\rnode{whitepausing}{\psframebox{pausing white}}}
\pcline{**->}(3.5,13.7)(4,13.3)
\pcline{->}(3.2,11.3)(3.2,12.7)\Aput{\tiny black\_moves}
\pcline{->}(3.7,12.7)(3.7,11.3)\Aput{\tiny tick [white = 0] / black\_wins}
\pcline{<-}(5.4,11)(7.6,11)
\pcline(7.6,11)(7.6,12.8)\Bput{\tiny white\_moves / white := white + 12}
\pcline(7.6,12.8)(5.4,12.8)
\ncloop[angleB=180]{->}{whiterunning}{whiterunning}\Bput{\tiny tick [white $>$ 0] / white := white - 1}
\psline[linestyle=dashed](0,10)(12,10)
\rput(4,8){\rnode{blackrunning}{\psframebox{running black}}}
\rput(4,6){\rnode{blackpausing}{\psframebox{pausing black}}}
\pcline{**->}(3.5,5.2)(4,5.7)
\pcline{->}(3.2,6.3)(3.2,7.7)\Aput{\tiny white\_moves}
\pcline{->}(3.7,7.7)(3.7,6.3)\Aput{\tiny tick [black = 0] / white\_wins}
\pcline{<-}(5.4,6)(7.6,6)
\pcline(7.6,6)(7.6,7.8)\Bput{\tiny black\_moves / black := black + 12}
\pcline(7.6,7.8)(5.4,7.8)
\ncloop[angleB=180]{->}{blackrunning}{blackrunning}\Bput{\tiny tick [black $>$ 0] / black := black - 1}
\psline[linestyle=dashed](0,5)(12,5)
\rput(6,3){\rnode{timer}{\psshadowbox{1 sec}}}
\ncloop[angleB=180,loopsize=1]{->}{timer}{timer}\Bput{\tiny timeout/tick}
\rput(6,0){\rnode{off}{\psframebox{off}}}
\pcline{->}(5.8,0.3)(3,2)\Aput{\tiny key\_on / white := 300, black := 300}
\pcline{->}(9,2)(6.2,0.3)\Aput{\tiny key\_off}
\end{pspicture}
\end{center}
%(d)
\newpage
\item We create one big OR superstate which contains the AND superstates of the exercise parts a, b and c. These are marked as boxed letters
for the sake of readability. Our solution looks like this:
\begin{center}
\begin{pspicture}(0,0)(12,10)
\psframe(0,2)(12,10)
\rput(1.7,6){\ovalnode{start}{start}}
\pcline{**->}(0.2,6)(1,6)
\rput(11.5,9.5){\rnode{a}{\psframebox{a}}}
\ncline{->}{start}{a}\Aput{\tiny [gt = classic] / white := 7200, black := 7200, wm := 40, bm := 40}
\rput(11.5,6){\rnode{b}{\psframebox{b}}}
\ncline{->}{start}{b}\Aput{\tiny \ \ \ [gt = quickplay] / white := 7200, black := 7200, wm := 40, bm := 40}
\rput(11.5,2.5){\rnode{c}{\psframebox{c}}}
\ncline{->}{start}{c}\Bput{\tiny [gt = fischer] / white := 300, black := 300}
\rput(6,0){\rnode{off}{\psframebox{off}}}
\pcline{->}(5.6,0.0)(0.5,2)\Aput{\tiny key\_on\_c / gt := classic}
\pcline{->}(5.7,0.3)(5,2)%\Aput{\tiny key\_on\_q / gt := quickplay}
\rput(4.5,1.5){\tiny key\_on\_q /}
\rput(4.4,1.2){\tiny gt := quickplay}
\pcline{->}(6.3,0.3)(7.5,2)%\Bput{\tiny key\_on\_f / gt := fischer}
\rput(7.9,1.5){\tiny key\_on\_f /}
\rput(7.8,1.2){\tiny gt := fischer}
\pcline{->}(11.5,2)(6.4,0.0)\Aput{\tiny key\_off}
\end{pspicture}
\end{center}
\end{enumerate}
In this (whole) exercise we used some variables, which we want to explain here:
\begin{itemize}
\item white, black \\
The number of seconds left to the white and the black player.
\item wm, bm \\
The number of moves left to the white and the black player. This is needed to determine whether the player is still whithin his first 40 moves
or not.
\item gt \\
This simply stands for gametype.
\end{itemize}

\exercise{Petri nets}
\begin{center}
\begin{pspicture}(0,0)(11,8)
\rput(1,7){\ovalnode{c1}{$c_1$}}
\rput(4,7){\rnode{e1}{\psframebox{$e_1$}}}
\rput(4,4){\rnode{e2}{\psframebox{$e_2$}}}
\rput(7,7){\ovalnode{c2}{$c_2$}}
\rput(7,4){\ovalnode{c3}{$c_3$}}
\rput(7,1){\ovalnode{c4}{$c_4$}}
\rput(10,7){\rnode{e3}{\psframebox{$e_3$}}}
\ncline{->}{c1}{e1}
\ncline{->}{c1}{e2}
\ncline{->}{e1}{c2}
\ncline{->}{e1}{c3}
\ncline{->}{e2}{c3}
\ncline{->}{e2}{c4}
\ncline{->}{c2}{e3}
\ncline{->}{c3}{e3}
\ncline{->}{c4}{e3}
\ncbar[nodesep=3pt,angle=90]{->}{e3}{c1}
\end{pspicture}
\end{center}
The preconditions of $e_3$ are: $\{c_2, c_3, c_4\}$. \\
The postconditions of $e_1$ are: $\{c_2, c_3\}$. \\
The net is pure, because it does not contain any loops. The net is simple, because $e_1$ and $e_2$ have the same set of preconditions, namely $\{c_1\}$,
but do not have the same set of postconditions.

\newpage
\exercise{Petri nets}
The following abbreviations are used: \\
M. for Milan, V. for Villa San Giovanni, M.M. for Messina Marittima, M.C. for Messina Centrale, S. for Siracusa and P. for Palermo.
\begin{center}
\bild{16}{problem3}
\end{center}

\exercise{Petri nets}
\begin{center}
\begin{pspicture}(0,0)(10,7)
\rput(0,6){\ovalnode{00}{\phantom{x}}}
\rput(2,6){\rnode{01}{\psframebox{\phantom{x}}}}
\rput(4,6){\ovalnode{02}{\phantom{x}}}
\rput(6,6){\rnode{03}{...}}
\rput(8,6){\ovalnode{04}{\phantom{x}}}
\rput(0,4){\rnode{10}{\psframebox{\phantom{x}}}}
\rput(4,4){\rnode{11}{\psframebox{\phantom{x}}}}
\rput(6,4){...}
\rput(8,4){\rnode{12}{\psframebox{\phantom{x}}}}
\rput(0,2){\rnode{20}{$N_0$}}
\rput(4,2){\rnode{21}{$N_1$}}
\rput(6,2){...}
\rput(8,2){\rnode{22}{$N_k$}}
\rput(10,6){\rnode{05}{...}}
\rput(10,4){...}
\rput(10,2){\rnode{23}{...}}
\ncline{->}{00}{01}
\ncline{->}{01}{02}
\ncline{->}{02}{03}
\ncline{->}{03}{04}
\ncline{->}{00}{10}
\ncline{->}{02}{11}
\ncline{->}{04}{12}
\ncline{->}{10}{20}
\ncline{->}{11}{21}
\ncline{->}{12}{22}
\ncline{->}{04}{05}
\end{pspicture}
\end{center}

\exercise{Petri nets}
\begin{enumerate}
\item \ \\
\begin{center}
\begin{pspicture}(0,0)(4,2)
\rput(0,2){\ovalnode{x}{x}}
\rput(2,2){\rnode{t1}{\psframebox{$t_1$}}}
\rput(4,1){\ovalnode{z}{z}}
\rput(0,0){\ovalnode{y}{y}}
\rput(2,0){\rnode{t2}{\psframebox{$t_2$}}}
\ncline{->}{x}{t1}\Aput{1}
\ncline{->}{t1}{z}\Aput{1}
\ncline{->}{y}{t2}\Aput{1}
\ncline{->}{t2}{z}\Aput{1}
\end{pspicture}
\end{center}
\item \ \\
\begin{center}
\begin{pspicture}(0,0)(4,4)
\rput(0,4){\ovalnode{x}{x}}
\rput(2,4){\rnode{t1}{\psframebox{$t_1$}}}
\rput(4,4){\ovalnode{z}{z}}
\rput(0,2){\ovalnode{y}{y}}
\rput(3,2){\rnode{t2}{\psframebox{$t_2$}}}
\rput(3,0){\ovalnode{tr}{trash}}
\ncline{->}{x}{t1}\Aput{1}
\ncline{->}{t1}{z}\Aput{1}
\ncline{->}{y}{t2}\Aput{1}
\ncline{->}{z}{t2}\Aput{1}
\ncline{->}{t2}{tr}\Aput{1}
\end{pspicture}
\end{center}
\item \ \\
\begin{center}
\begin{pspicture}(0,0)(4,0)
\rput(0,0){\ovalnode{rest}{x}}
\rput(2,0){\rnode{t1}{\psframebox{$t_1$}}}
\rput(4,0){\ovalnode{div}{div}}
\ncline{->}{rest}{t1}\Aput{7}
\ncline{->}{t1}{div}\Aput{1}
\end{pspicture}
\end{center}
\end{enumerate}

\end{document}
