\documentclass[12pt,fleqn,a4j]{jarticle}
\title{�y�g���l�b�g����}
\author{���c �~}
\date{1995�N4��18��}
\newcounter{exercise}
\newenvironment{exercise}{\refstepcounter{exercise} \begin{trivlist} \item[\hskip \labelsep{{\bf ��� \theexercise}}]}{\end{trivlist}}
\newcounter{answer}
\newenvironment{answer}{\refstepcounter{answer} \begin{trivlist} \item[\hskip \labelsep{{\bf ��� \theanswer}}]}{\end{trivlist}}
\newcounter{example}[section]
\renewcommand{\theexample}{\arabic{section}.\arabic{example}}
\newenvironment{example}{\refstepcounter{example} \begin{trivlist} \item[\hskip \labelsep{{\bf �� \theexample}}]}{\end{trivlist}}
\newcounter{definition}
\newenvironment{definition}[1]{\refstepcounter{definition} \begin{trivlist} \item[\hskip \labelsep{[{\bf ��` \thedefinition }]}] #1\nopagebreak\par}{$\square$ \end{trivlist}}
\newcommand{\yen}{\makebox[0pt][l]{=}Y}
\newcommand{\txtsum}{\mathop{\textstyle\sum}}
%------------------------------------------------------------------------------
\begin{document}
\maketitle
\section{���U���ۃV�X�e���ƃy�g���l�b�g}
����V�X�e���̐�������͂�����A���䂵���肷��ɂ́A
�ΏۂƂ���V�X�e���̐����ɍ��������f����p���邱�Ƃ��L���ł���B
�Ⴆ�΁A���`���s�σV�X�e���ɂ́A
�`�B�֐����ԋ�ԃ��f���Ȃǂ��p�����Ă���B

�y�g���l�b�g(Petri net)�́u���U���ۃV�X�e��(discrete event system)�v��
�Ă΂��V�X�e���̂��߂̃��f���̈�ł���B

���U���ۃV�X�e���̈��Ƃ��āA�d�b���l���Ă݂�B
A�͎�b����グ�ă_�C��������B
������B���o��Θb�����ēd�b��؂�B�o�Ȃ���΂��̂܂ܓd�b��؂�B
���̗l�q��}\ref{fig:phoneA}(a)�ŕ\���B
A����d�b���������Ă���ƁAB�̃x������B
B����b����Ƃ�΁AA�Ƙb�����āA�d�b��؂�B
���̑O�ɁAA���d�b��؂邩������Ȃ��B
���̗l�q��}\ref{fig:phoneA}(b)�ŕ\���B
\begin{figure}[htb]
\centering
\setlength{\unitlength}{0.6pt}%
\small%
\begin{picture}(300,300)(0,-20)%
\thicklines%
\put(150,260){\oval(140,20)}%
\put(80,210){\framebox(140,20){}}%
\put(150,180){\oval(140,20)}%
\put(0,130){\framebox(140,20){}}%
\put(160,130){\framebox(140,20){}}%
\put(230,100){\oval(140,20)}%
\put(160,50){\framebox(140,20){}}%
\put(150,20){\oval(140,20)}%
\thinlines%
\put(150,250){\vector(0,-1){20}}%
\put(150,210){\vector(0,-1){20}}%
\put(100,170){\vector(-1,-1){20}}%
\put(200,170){\vector(1,-1){20}}%
\put(230,130){\vector(0,-1){20}}%
\put(230,90){\vector(0,-1){20}}%
\put(80,130){\vector(1,-2){50}}%
\put(190,50){\vector(-1,-1){20}}%
\put(150,260){\makebox(0,0){A:�ҋ@��}}%
\put(150,220){\makebox(0,0){A���d�b��������}}%
\put(150,180){\makebox(0,0){�ďo��}}%
\put(70,140){\makebox(0,0){A���d�b��؂�}}%
\put(230,100){\makebox(0,0){�ʘb��}}%
\put(230,60){\makebox(0,0){A���d�b��؂�}}%
\put(150,20){\makebox(0,0){A:�ҋ@��}}%
\put(230,140){\makebox(0,0){B���o��}}%
\put(0,-20){\makebox(300,20){(a)}}%
\end{picture}%
\hspace{2zw}
\setlength{\unitlength}{0.6pt}%
\small%
\begin{picture}(300,300)(0,-20)%
\thicklines%
\put(150,260){\oval(140,20)}%
\put(80,210){\framebox(140,20){}}%
\put(150,180){\oval(140,20)}%
\put(0,130){\framebox(140,20){}}%
\put(160,130){\framebox(140,20){}}%
\put(230,100){\oval(140,20)}%
\put(160,50){\framebox(140,20){}}%
\put(150,20){\oval(140,20)}%
\thinlines%
\put(150,250){\vector(0,-1){20}}%
\put(150,210){\vector(0,-1){20}}%
\put(100,170){\vector(-1,-1){20}}%
\put(200,170){\vector(1,-1){20}}%
\put(230,130){\vector(0,-1){20}}%
\put(230,90){\vector(0,-1){20}}%
\put(80,130){\vector(1,-2){50}}%
\put(190,50){\vector(-1,-1){20}}%
\put(150,260){\makebox(0,0){B:�ҋ@��}}%
\put(150,220){\makebox(0,0){A���d�b��������}}%
\put(150,180){\makebox(0,0){�ďo�x��}}%
\put(70,140){\makebox(0,0){A���d�b��؂�}}%
\put(230,100){\makebox(0,0){�ʘb��}}%
\put(230,60){\makebox(0,0){B���d�b��؂�}}%
\put(150,20){\makebox(0,0){B:�ҋ@��}}%
\put(230,140){\makebox(0,0){B���o��}}%
\put(0,-20){\makebox(300,20){(b)}}%
\end{picture}%
\caption{�d�b��������}
\label{fig:phoneA}
\end{figure}

�}���A{\setlength{\unitlength}{1zw}
\begin{picture}(1,0.8)(0,0)\put(0,0){\framebox(1,0.8){}}\end{picture}}
��A�܂���B�̓���A
{\setlength{\unitlength}{1zw}
\begin{picture}(1,0.8)(0,0)\put(0.5,0.4){\oval(1,0.8)}\end{picture}}
�͓d�b�̏�Ԃ�\���B

���́u�V�X�e���v�̓����������������Ă݂�B
�܂��A�d�b�̏�Ԃ͕s�A���ł���B
�Ⴆ�΁A�x���͖��Ă��邩���Ȃ����̂����ꂩ�ł����āA
�u15.4\%���Ă���v�Ƃ������Ƃ͂Ȃ��B
�x�������Ă���Ƃ��AA���d�b��؂�Ȃ�����́AB�͂��d�b�ɏo�Ă��悢�B
�ʘb���I�������(�Ƃ͌���Ȃ�?)�AA��B�͂ǂ��炪��Ɏ�b���u���Ă��悢�B
���ɏq�ׂ�悤�ɁA�����͗��U���ۃV�X�e��������Â��鐫���ł���B

�`���I�ɂ́A���U���ۃV�X�e���Ƃ́A�v�ʂ̓���Ȃ��ϐ��ŕ\�����V�X�e���ł���B
���U���ۃV�X�e���ɂ������Ԃ̑J�ڂ��u����(event)�̐��N�v�Ƃ����B
��̏��A��B�́u���Ԃ́v��Ԃ͑��݂��Ȃ��̂ŁA���ۂ̐��N�͏u���ɋN����B
���U���ۃV�X�e���ɂ́A�ʏ�̈Ӗ��ł́u���v�v�͑��݂��Ȃ��B
���ۂ̊Ԃɔ������֌W(��������`����Ă��Ȃ��g�������Ă��悢�_��������
�ʏ�́u�S�����v�Ɠ������̂ƍl���Ă悢)�����݂���݂̂ł���B
���̏����ɔ����Ă��Ȃ����
���N�\�Ȏ��ۂ͂����N���Ă��悢(�񓯊���, asynchronousness)���A
�����̒�`����Ă��Ȃ���̎��ۂ́A�ǂ��炪��ɐ��N���Ă��悢
(�����i�s��, concurrency: Petri�͑��ΐ����_�܂ł��������Đ������Ă���!)�B
\begin{exercise}
���U���ۃV�X�e���̗��������B
\end{exercise}
%------------------------------------------------------------------------------
\section{�y�g���l�b�g}
\subsection{�y�g���l�b�g�̒�`}
�y�g���l�b�g�́A�v���[�X(place)�A�g�����W�V����(transition)�Ƃ���
���ނ̃m�[�h(node)�����񕔗L���O���t(bipartite digraph)�ł���B
�v���[�X�͉~�ŕ\�����m�[�h�ł���A������\���B
�g�����W�V�����͖_�܂��͔��ŕ\�����m�[�h�ł���A���ۂ�\���B
���������ԃA�[�N(arc)�͏����A���ۂ̊Ԃ̊֌W��\���B
�v���[�X�A�g�����W�V�����A�A�[�N���V�X�e���̍\����\������B
�A�[�N�ɂ͐������̏d�݂�������ꍇ������B
�d�݂̓A�[�N�̖{���ŕ\�����A�A�[�N�ɏd�݂𕹋L���ĕ\���B
�d�݂������Ȃ��A�[�N�͏d�݂�1�ł���Ƃ݂Ȃ��B
�v���[�X�̏�ɂ́A�񕉐����̃g�[�N��(token)���u�����B
�g�[�N���͓_�ŕ\����A�����̐�����\���B
�v���[�X��̃g�[�N���̔z�u���}�[�L���O(marking)�Ƃ����A�V�X�e���̏�Ԃ�\���B

�`���I�ɂ́A�y�g���l�b�g�� $N=(P,\,T,\,F,\,W,\,m_0)$ �ŕ\�����B
\[\left\{\mbox{%
\begin{tabular}{ll}
$P=\{p_1,\,p_2,\,\ldots,\,p_{|P|}\}$
	& �v���[�X�̗L���W��($|P|$; �v���[�X�̐�)\\
$T=\{t_1,\,t_2,\,\ldots,\,t_{|T|}\}$
	& �g�����W�V�����̗L���W��($|T|$; �g�����W�V�����̐�)\\
$F \subseteq (P\times T)\cup(T\times P)$ & �A�[�N�̏W��\\
$W: F \mapsto \{1,\,2,\,\ldots\,\}$ & �A�[�N�̏d��\\
$m_0: P \mapsto \{ 0,\,1,\,2,\,\ldots\,\}$ & �����}�[�L���O
\end{tabular}}
\right.\]
�}�[�L���O�̓x�N�g���̌`�ŁA%
$m_0=[m_0(p_1)\,m_0(p_2)\,\cdots\,m_0(p_{|P|})]^T$ �̂悤�ɕ\�����Ƃ��ł���B

�g�����W�V���� $t$ �Ɍ������A�[�N�� $t$ �̓��̓A�[�N�A
$t$ �̓��̓A�[�N���o�čs�����Ƃ̃v���[�X�� $t$ �̓��̓v���[�X�Ƃ����B
$t$ ����o�čs���A�[�N���o�̓A�[�N�A
$t$ �̏o�̓A�[�N�������čs����̃v���[�X�� $t$ �̏o�̓v���[�X�Ƃ����B
�v���[�X $p$ �̓��o�̓A�[�N�A���o�̓g�����W�V�������܂����l�ɒ�`����B
\begin{example}
�}\ref{fig:pnexpl1}�̃y�g���l�b�g�́A\\
�@$P=\{ p_1,\,p_2,\,p_3,\,p_4 \}$\\
�@$T=\{ t_1,\,t_2,\,t_3 \}$\\
�@$F=\{(p_1,t_1),\,(p_2,t_1),\,(p_3,t_2),\,(p_4,t_2),\,(p_4,t_3),\,
(t_1,p_3),\,(t_1,p_4),\,(t_2,p_2),\,(t_3,p_1),\,(t_3,p_4)\}$\\
�@$W((p_1,t_1))=3,\,W((p_3,t_2))=2,\,
W((p_2,t_1))=\cdots=W((t_3,p_4))=1$\\
�@$m_0(p_1)=3,\,m_0(p_2)=2,\,m_0(p_3)=1,\,m_0(p_4)=1$\\
�ƕ\�����B
\begin{figure}[htb]
\centering
\setlength{\unitlength}{0.5pt}%
\begin{picture}(260,180)(0,0)%
\thicklines%
\put(20,120){\circle{40}}%
\put(100,150){\line(0,-1){60}}%
\put(180,30){\circle{40}}%
\put(100,60){\line(0,-1){60}}%
\put(260,150){\line(0,-1){60}}%
\thinlines%
\put(40,120){\vector(1,0){60}}%
\put(163,40){\vector(-1,0){63}}%
\put(100,20){\vector(1,0){63}}%
\put(20,40){\vector(0,1){60}}%
\put(100,100){\vector(4,-3){70}}%
\put(188,48){\vector(4,3){72}}%
\thicklines%
\put(180,160){\circle{40}}%
\put(180,100){\circle{40}}%
\thinlines%
\put(100,115){\vector(4,-1){60}}%
\put(200,100){\vector(4,1){59}}%
\put(198,107){\vector(4,1){62}}%
\put(100,40){\oval(160,20)[bl]}%
\put(30,90){$p_1$}%
\put(200,175){$p_2$}%
\put(200,120){$p_3$}%
\put(200,10){$p_4$}%
\put(94,155){$t_1$}%
\put(94,-20){$t_3$}%
\put(253,70){$t_2$}%
\put(65,123){3}%
\put(20,130){\circle*{10}}%
\put(11,115){\circle*{10}}%
\put(27,115){\circle*{10}}%
\put(173,166){\circle*{10}}%
\put(185,155){\circle*{10}}%
\put(180,30){\circle*{10}}%
\put(180,100){\circle*{10}}%
\put(260,135){\vector(-2,1){59}}%
\put(159,166){\vector(-2,-1){58}}%
\end{picture}%
\caption{�y�g���l�b�g}
\label{fig:pnexpl1}
\end{figure}
�}�[�L���O���x�N�g���̌`�ŕ\���ƁA$m_0=[3\,2\,1\,1]^T$ �ƂȂ�B
$t_1$ �̓��̓v���[�X�� $\{p_1\,p_2\}$�A�o�̓v���[�X�� $\{p_3,\,p_4\}$ �ł���B
$p_1$ �̓��̓g�����W�V������ $\{t_3\}$�A�o�̓g�����W�V������ $\{t_1\}$ �ł���B
\end{example}
%
\subsection{�g�����W�V�����̔���}
�y�g���l�b�g�̃}�[�L���O�̓g�����W�V�����̔���(firing)�ɂ���đJ�ڂ���B
�g�����W�V���� $t$ ���}�[�L���O $m$ �Ŕ��Ή\(fireable, enabled)�ł���Ƃ́A
$t$ �̂��ׂĂ̓��̓v���[�X�����̓A�[�N�̏d�݈ȏ�̌��̃g�[�N����������
�ł���A$m[t\rangle$ �ŕ\���B
���Ή\�ȃg�����W�V�����͔��΂��Ă����Ȃ��Ă��悢�B
���Ή\�ȃg�����W�V���� $t$ �����΂���ƁA
�e���̓v���[�X������̓A�[�N�̏d�݂̐������̃g�[�N������苎��A
�e�o�̓v���[�X�ɏo�̓A�[�N�̏d�݂̐������̃g�[�N����^����B
���̌��ʂ̃}�[�L���O�� $m'$ �Ƃ���΁A$m[t\rangle m'$ �ƕ\�����B
\begin{example}
�}\ref{fig:pnexpl1}�̃y�g���l�b�g�ŁA$t_1$ �� $t_3$ �͔��Ή\�ł���B
$t_2$ �� $p_3$ �ɓ��̓A�[�N�̏d��2�ȏ�̃g�[�N�����Ȃ��̂ŁA���Ή\�ł͂Ȃ��B
$t_1$ �����΂������ʂ̃}�[�L���O�� $m_1$ �Ƃ���΁A
$m_1=[0\,1\,2\,2]^T$ �ł���B
\end{example}
\subsection{�����i�s�Ƌ���}
�}�[�L���O $m$ ��
2�̃g�����W�V���� $t$�A$t'$ �����Ή\�ł�����̂Ƃ���B
�����̃g�����W�V������ $m$ ���� $t$�A$t'$ �̏��ɂ��A$t'$�A$t$ �̏��ɂ�
�������΂ł���Ƃ��A
$t$ �� $t'$ �͓������Ή\(simultaneously enabled)�ł���Ƃ����B
�����łȂ��Ƃ��A $t$ �� $t'$ �͋���(conflict)�̏�Ԃɂ���Ƃ����B
\begin{example}
�}\ref{fig:conflict}�̃y�g���l�b�g�ŁA
$t_1$�A$t_2$�A$t_3$ �͂Ƃ��ɔ��Ή\�ł���B
$t_1$ �� $t_3$ �͓������Ή\�ł��邪�A
$t_1$ �� $t_2$�A$t_2$ �� $t_3$ �͋����̊֌W�ɂ���B
\begin{figure}[htb]
\centering
\setlength{\unitlength}{0.5pt}%
\begin{picture}(240,140)(0,0)%
\thicklines%
\put(0,20){\line(1,0){60}}%
\put(90,20){\line(1,0){60}}%
\put(180,20){\line(1,0){60}}%
\put(70,100){\circle{40}}%
\put(170,100){\circle{40}}%
\thinlines%
\put(58,85){\vector(-1,-2){32}}%
\put(81,83){\vector(1,-3){21}}%
\put(160,82){\vector(-1,-3){20}}%
\put(182,84){\vector(1,-3){21}}%
\put(213,21){\vector(-1,3){24}}%
\put(70,100){\circle*{10}}%
\put(170,100){\circle*{10}}%
\put(40,0){$t_1$}%
\put(130,0){$t_2$}%
\put(220,0){$t_3$}%
\put(68,130){$p_1$}%
\put(168,130){$p_2$}%
\end{picture}%
\caption{�����i�s�Ƌ���}
\label{fig:conflict}
\end{figure}
\end{example}
\begin{exercise}
�}\ref{fig:pnexpl2}�̃y�g���l�b�g�ŁA\\
�@1. �}�̃}�[�L���O $m_0$ ���甭�Ή\�ȃg�����W�V�����͂ǂꂩ�B\\
�@2. $m_0$ ���甭�Ή\�ȃg�����W�V���������ꂼ�ꔭ�΂��������ʂ̃}�[�L���O�������B\\
�@3. $m_0$ �ŋ����֌W�ɂ���g�����W�V�����͂ǂ�Ƃǂꂩ�B
\begin{figure}[htb]
\centering
\setlength{\unitlength}{0.5pt}%
\begin{picture}(270,140)(0,0)%
\thicklines%
\put(20,110){\circle{40}}%
\put(100,140){\line(0,-1){60}}%
\put(180,110){\circle{40}}%
\put(260,140){\line(0,-1){60}}%
\put(20,30){\circle{40}}%
\put(180,30){\circle{40}}%
\put(100,60){\line(0,-1){60}}%
\put(260,60){\line(0,-1){60}}%
\thinlines%
\put(40,115){\vector(1,0){60}}%
\put(40,105){\vector(1,0){60}}%
\put(100,110){\vector(1,0){60}}%
\put(200,115){\vector(1,0){60}}%
\put(201,105){\vector(1,0){60}}%
\put(40,30){\vector(1,0){60}}%
\put(100,30){\vector(1,0){60}}%
\put(200,30){\vector(1,0){60}}%
\put(36,99){\vector(4,-3){62}}%
\put(162,43){\vector(-4,3){61}}%
\put(196,42){\vector(4,3){62}}%
\put(197,101){\vector(4,-3){62}}%
\put(100,53){\vector(4,3){63}}%
\put(142,70){3}%
\put(30,135){$p_1$}%
\put(190,135){$p_2$}%
\put(30,0){$p_3$}%
\put(190,0){$p_4$}%
\put(105,140){$t_1$}%
\put(265,140){$t_2$}%
\put(105,-20){$t_3$}%
\put(265,-20){$t_4$}%
\put(180,110){\circle*{10}}%
\put(180,30){\circle*{10}}%
\put(20,30){\circle*{10}}%
\put(20,120){\circle*{10}}%
\put(12,106){\circle*{10}}%
\put(29,107){\circle*{10}}%
\end{picture}%
\caption{�y�g���l�b�g}
\label{fig:pnexpl2}
\end{figure}
\end{exercise}
%
\subsection{�y�g���l�b�g�ƃ��f����}
�ȉ��ɁA3�̃��f�����̗��������B
�y�g���l�b�g�̃��f���Ƃ��Ă̓����ɂ��ӂ��B
\begin{example}
�}\ref{fig:vendor}�ɊȒP�ȃW���[�X�̎����̔��@�̃��f���������B
�q��110�~�܂���200�~�𓊓����A�{�^���������B
���̌��ʁA�W���[�X�ƒނ�K���o�Ă���B
\begin{figure}[htbp]
\centering
\small
\setlength{\unitlength}{0.5pt}%
%\newcommand{\yen}{\makebox[0pt][l]{=}Y}%
\small%
\begin{picture}(350,360)(0,0)%
\thicklines%
\put(270,190){\circle{40}}%
\thinlines%
\put(220,200){\vector(1,0){30}}%
\put(140,190){\vector(1,0){110}}%
\put(60,180){\vector(1,0){190}}%
\put(60,230){\oval(20,100)[bl]}%
\put(140,230){\oval(20,80)[bl]}%
\put(220,230){\oval(20,60)[bl]}%
\thicklines%
\put(270,140){\circle{40}}%
\put(190,140){\circle{40}}%
\put(110,140){\circle{40}}%
\thinlines%
\put(190,230){\vector(0,-1){70}}%
\put(110,230){\vector(0,-1){70}}%
\put(40,140){\vector(1,0){50}}%
\put(40,230){\oval(20,180)[bl]}%
\thicklines%
\put(60,230){\line(-1,0){60}}%
\put(80,230){\line(1,0){60}}%
\put(160,230){\line(1,0){60}}%
\put(110,290){\circle{40}}%
\put(190,290){\circle{40}}%
\thinlines%
\put(190,270){\vector(0,-1){40}}%
\put(110,270){\vector(0,-1){40}}%
\put(174,278){\vector(-1,-1){47}}%
\put(93,277){\vector(-4,-3){63}}%
\thicklines%
\put(80,350){\line(1,0){60}}%
\put(160,350){\line(1,0){60}}%
\put(260,350){\line(1,0){60}}%
\thinlines%
\put(270,210){\vector(0,1){140}}%
\put(190,350){\vector(0,-1){40}}%
\put(110,350){\vector(0,-1){40}}%
\thinlines%
\put(300,140){\vector(-1,0){10}}%
\put(300,350){\oval(20,420)[br]}%
\thicklines%
\put(80,80){\line(1,0){60}}%
\put(160,80){\line(1,0){60}}%
\thinlines%
\put(110,120){\vector(0,-1){40}}%
\put(190,120){\vector(0,-1){40}}%
\put(254,125){\vector(-3,-1){130}}%
\put(262,121){\vector(-3,-2){58}}%
\thicklines%
\put(110,20){\circle{40}}%
\put(190,20){\circle{40}}%
\thinlines%
\put(190,80){\vector(0,-1){40}}%
\put(110,80){\vector(0,-1){40}}%
\put(170,80){\vector(-1,-1){45}}%
\put(200,50){9}%
\put(200,250){2}%
\put(50,260){11}%
\put(120,355){\yen 10}%
\put(200,355){\yen 100}%
\put(300,355){button}%
\put(50,110){\yen 110}%
\put(130,110){\yen 200}%
\put(45,0){juice}%
\put(210,0){\yen 10}%
\put(95,305){\makebox(0,0)[br]{$p_1$}}%
\put(175,305){\makebox(0,0)[br]{$p_2$}}%
\put(255,210){\makebox(0,0)[br]{$p_3$}}%
\put(285,125){\makebox(0,0)[tl]{$p_4$}}%
\put(0,225){\makebox(0,0)[tl]{$t_1$}}%
\put(80,225){\makebox(0,0)[tl]{$t_2$}}%
\put(160,225){\makebox(0,0)[tl]{$t_3$}}%
\put(80,75){\makebox(0,0)[tl]{$t_4$}}%
\put(220,75){\makebox(0,0)[tl]{$t_5$}}%
\end{picture}%
\caption{�����̔��@�̃��f��}
\label{fig:vendor}
\end{figure}

`\yen 10'�A`\yen 100'�A`button' �ƃ��x���Â����ꂽ�g�����W�V������
���ꂼ��A10�~�d�݂𓊓�����A100�~�d�݂𓊓�����A�{�^�������������\���B
$p_1$�A$p_2$ �͂��ꂼ��A�������ꂽ10�~�d�݁A100�~�d�݂��g�[�N���Ƃ��Ă��B
$t_1$�A$t_2$�A$t_3$ �͂��ꂼ��A10�~��11���A10�~��1����100�~��1���A100�~��2��
���������Ɣ��Ή\�ƂȂ�B
$p_3$ �͏\���ȋ��z����������Ă��āA
�{�^���������΃W���[�X���o�Ă��邱�Ƃ�\���Ă���B
���̂Ƃ��{�^�����������ƁA$p_4$ �Ƀg�[�N������������A
�������z��110�~��200�~���ɂ���āA$t_4$ �܂��� $t_5$ �����΂���B
$t_4$ �����΂���΃W���[�X�݂̂��A
$t_5$ �����΂���΃W���[�X�ƒނ�K90�~���A
`juice'�A`\yen 10'�̃v���[�X�ɓ��������B
\end{example}
%
\begin{example}
�}\ref{fig:flowshop}(a)�͐��Y�V�X�e���̃��f���ł���B
2��ނ̐��i1�A2�����ꂼ��@�BA�AB�ɉ��H����Ċ�������B
$p_a$�A$p_b$ �͂��ꂼ��A�@�BA�AB�����H���łȂ��A�g�p�\�ł��邱�Ƃ�\���B
$p_{is}$ $(i=1,2)$ �͐��i $i$ �̉��H�������ł��Ă��邱�Ƃ������B
$p_{ia}$�A$p_{ib}$ $(i=1,2)$ �͂��ꂼ��A
���i $i$ ���@�BA�AB�ŉ��H�����ł��邱�Ƃ������B
$p_{it}$ $(i=1,2)$ �͐��i $i$ ���@�BA�̂���ꏊ����
�@�BB�̂���ꏊ�։^�΂�Ă��邱�Ƃ������B
$p_{if}$ $(i=1,2)$ �͐��i $i$ �̉��H���I���������Ƃ������B
$t_{ias}$�A$t_{ibs}$ $(i=1,2)$ �͂��ꂼ��A
���i $i$ �̋@�BA�AB�ɂ����H���J�n���邱�Ƃ�\���A
$t_{iaf}$�A$t_{ibf}$ $(i=1,2)$ �͉��H�̏I����\���B
\begin{figure}[htbp]
\centering
\setlength{\unitlength}{0.5pt}
\begin{picture}(720,520)(0,0)
\put(0,320){%
\begin{picture}(440,180)(0,0)%
\thicklines%
\put(20,150){\circle{40}}%
\put(70,180){\line(0,-1){60}}%
\put(120,150){\circle{40}}%
\put(170,180){\line(0,-1){60}}%
\put(220,150){\circle{40}}%
\put(270,180){\line(0,-1){60}}%
\put(320,150){\circle{40}}%
\put(370,180){\line(0,-1){60}}%
\put(420,150){\circle{40}}%
\thinlines%
\put(40,150){\vector(1,0){30}}%
\put(70,150){\vector(1,0){30}}%
\put(140,150){\vector(1,0){30}}%
\put(170,150){\vector(1,0){30}}%
\put(240,150){\vector(1,0){30}}%
\put(270,150){\vector(1,0){30}}%
\put(340,150){\vector(1,0){30}}%
\put(370,150){\vector(1,0){30}}%
\thicklines%
\put(120,90){\circle{40}}%
\put(20,30){\circle{40}}%
\put(70,60){\line(0,-1){60}}%
\put(120,30){\circle{40}}%
\put(170,60){\line(0,-1){60}}%
\put(220,30){\circle{40}}%
\put(270,60){\line(0,-1){60}}%
\put(320,30){\circle{40}}%
\put(370,60){\line(0,-1){60}}%
\put(420,30){\circle{40}}%
\thinlines%
\put(40,30){\vector(1,0){30}}%
\put(70,30){\vector(1,0){30}}%
\put(140,30){\vector(1,0){30}}%
\put(170,30){\vector(1,0){30}}%
\put(240,30){\vector(1,0){30}}%
\put(270,30){\vector(1,0){30}}%
\put(340,30){\vector(1,0){30}}%
\put(370,30){\vector(1,0){30}}%
\thinlines%
\put(170,130){\vector(-1,-1){31}}%
\put(170,50){\vector(-1,1){31}}%
\put(101,100){\vector(-1,1){31}}%
\put(101,82){\vector(-1,-1){32}}%
\put(120,90){\circle*{10}}%
\put(20,150){\circle*{10}}%
\put(20,30){\circle*{10}}%
\thicklines%
\put(320,90){\circle{40}}%
\thinlines%
\put(370,130){\vector(-1,-1){31}}%
\put(370,50){\vector(-1,1){31}}%
\put(301,100){\vector(-1,1){31}}%
\put(301,82){\vector(-1,-1){32}}%
\put(320,90){\circle*{10}}%
\put(150,83){$p_a$}%
\put(350,83){$p_b$}%
\put(20,180){$p_{1s}$}%
\put(120,180){$p_{1a}$}%
\put(220,180){$p_{1t}$}%
\put(320,180){$p_{1b}$}%
\put(420,180){$p_{1f}$}%
\put(70,185){$t_{1as}$}%
\put(170,185){$t_{1af}$}%
\put(270,185){$t_{1bs}$}%
\put(370,185){$t_{1bf}$}%
\put(20,-5){$p_{2s}$}%
\put(120,-5){$p_{2a}$}%
\put(220,-5){$p_{2t}$}%
\put(320,-5){$p_{2b}$}%
\put(420,-5){$p_{2f}$}%
\put(70,-15){$t_{2as}$}%
\put(170,-15){$t_{2af}$}%
\put(270,-15){$t_{2bs}$}%
\put(370,-15){$t_{2bf}$}%
\end{picture}%
}%
\put(480,320){%
\begin{picture}(240,180)(0,0)%
\thicklines%
\put(20,150){\circle{40}}%
\put(70,180){\line(0,-1){60}}%
\put(120,150){\circle{40}}%
\put(170,180){\line(0,-1){60}}%
\put(220,150){\circle{40}}%
\thinlines%
\put(40,150){\vector(1,0){30}}%
\put(70,150){\vector(1,0){30}}%
\put(140,150){\vector(1,0){30}}%
\put(170,150){\vector(1,0){30}}%
\thicklines%
\put(70,90){\circle{40}}%
\put(170,90){\circle{40}}%
\put(120,120){\line(0,-1){60}}%
\thinlines%
\put(120,90){\vector(-1,0){30}}%
\put(150,90){\vector(-1,0){30}}%
\put(30,110){\vector(2,1){40}}%
\put(210,110){\vector(-2,-1){21}}%
\put(30,110){\line(5,-2){22}}%
\put(210,110){\line(-2,1){40}}%
\put(30,70){\line(2,1){22}}%
\thicklines%
\put(20,30){\circle{40}}%
\put(70,60){\line(0,-1){60}}%
\put(120,30){\circle{40}}%
\put(170,60){\line(0,-1){60}}%
\put(220,30){\circle{40}}%
\thinlines%
\put(40,30){\vector(1,0){30}}%
\put(70,30){\vector(1,0){30}}%
\put(140,30){\vector(1,0){30}}%
\put(170,30){\vector(1,0){30}}%
\put(30,70){\vector(2,-1){40}}%
\put(210,70){\vector(-2,1){22}}%
\put(210,70){\line(-2,-1){40}}%
\put(70,90){\circle*{10}}%
\put(20,83){$p_{va}$}%
\put(200,83){$p_{vb}$}%
\put(125,60){$t_{mv}$}%
%\put(20,180){$p_{1ts}$}%
\put(120,180){$p_{1t}$}%
%\put(220,180){$p_{1tf}$}%
%\put(20,-5){$p_{2ts}$}%
\put(120,-5){$p_{2t}$}%
%\put(220,-5){$p_{2tf}$}%
\put(70,185){$t_{1ts}$}%
\put(170,185){$t_{1tf}$}%
\put(70,-15){$t_{2ts}$}%
\put(170,-15){$t_{2tf}$}%
\end{picture}%
}%
\put(40,50){%
\begin{picture}(640,180)(0,0)%
\thicklines%
\put(20,150){\circle{40}}%
\put(70,180){\line(0,-1){60}}%
\put(120,150){\circle{40}}%
\put(170,180){\line(0,-1){60}}%
\put(220,150){\circle{40}}%
\put(270,180){\line(0,-1){60}}%
\put(320,150){\circle{40}}%
\put(370,180){\line(0,-1){60}}%
\put(420,150){\circle{40}}%
\put(470,180){\line(0,-1){60}}%
\put(520,150){\circle{40}}%
\put(570,180){\line(0,-1){60}}%
\put(620,150){\circle{40}}%
\thinlines%
\put(40,150){\vector(1,0){30}}%
\put(70,150){\vector(1,0){30}}%
\put(140,150){\vector(1,0){30}}%
\put(170,150){\vector(1,0){30}}%
\put(240,150){\vector(1,0){30}}%
\put(270,150){\vector(1,0){30}}%
\put(340,150){\vector(1,0){30}}%
\put(370,150){\vector(1,0){30}}%
\put(440,150){\vector(1,0){30}}%
\put(470,150){\vector(1,0){30}}%
\put(540,150){\vector(1,0){30}}%
\put(570,150){\vector(1,0){30}}%
\thicklines%
\put(120,90){\circle{40}}%
\put(270,90){\circle{40}}%
\put(370,90){\circle{40}}%
\put(320,120){\line(0,-1){60}}%
\put(520,90){\circle{40}}%
\thinlines%
\put(320,90){\vector(-1,0){30}}%
\put(350,90){\vector(-1,0){30}}%
\put(230,110){\vector(2,1){40}}%
\put(410,110){\vector(-2,-1){21}}%
\put(230,110){\line(5,-2){22}}%
\put(410,110){\line(-2,1){40}}%
\put(230,70){\line(2,1){22}}%
\thicklines%
\put(20,30){\circle{40}}%
\put(70,60){\line(0,-1){60}}%
\put(120,30){\circle{40}}%
\put(170,60){\line(0,-1){60}}%
\put(220,30){\circle{40}}%
\put(270,60){\line(0,-1){60}}%
\put(320,30){\circle{40}}%
\put(370,60){\line(0,-1){60}}%
\put(420,30){\circle{40}}%
\put(470,60){\line(0,-1){60}}%
\put(520,30){\circle{40}}%
\put(570,60){\line(0,-1){60}}%
\thinlines%
\put(40,30){\vector(1,0){30}}%
\put(70,30){\vector(1,0){30}}%
\put(140,30){\vector(1,0){30}}%
\put(170,30){\vector(1,0){30}}%
\put(240,30){\vector(1,0){30}}%
\put(270,30){\vector(1,0){30}}%
\put(340,30){\vector(1,0){30}}%
\put(370,30){\vector(1,0){30}}%
\put(440,30){\vector(1,0){30}}%
\put(470,30){\vector(1,0){30}}%
\put(540,30){\vector(1,0){30}}%
\thicklines%
\put(620,30){\circle{40}}%
\thinlines%
\put(570,30){\vector(1,0){30}}%
\put(170,130){\vector(-1,-1){31}}%
\put(170,50){\vector(-1,1){31}}%
\put(101,100){\vector(-1,1){31}}%
\put(101,82){\vector(-1,-1){32}}%
\put(570,130){\vector(-1,-1){31}}%
\put(570,50){\vector(-1,1){31}}%
\put(501,100){\vector(-1,1){31}}%
\put(501,82){\vector(-1,-1){32}}%
\put(230,70){\vector(2,-1){40}}%
\put(410,70){\vector(-2,1){22}}%
\put(410,70){\line(-2,-1){40}}%
\put(270,90){\circle*{10}}%
\put(120,90){\circle*{10}}%
\put(520,90){\circle*{10}}%
\put(20,150){\circle*{10}}%
\put(20,30){\circle*{10}}%
%\put(118,174){$p_{1A}$}%
%\put(120,-10){$p_{2A}$}%
%\put(518,174){$p_{1B}$}%
%\put(517,-9){$p_{2B}$}%
%\put(150,80){$p_A$}%
%\put(550,80){$p_B$}%
\put(150,83){$p_a$}%
\put(550,83){$p_b$}%
\put(20,180){$p_{1s}$}%
\put(120,180){$p_{1a}$}%
\put(320,180){$p_{1t}$}%
\put(520,180){$p_{1b}$}%
\put(620,180){$p_{1f}$}%
\put(70,185){$t_{1as}$}%
\put(170,185){$t_{1af}$}%
\put(270,185){$t_{1ts}$}%
\put(370,185){$t_{1tf}$}%
\put(470,185){$t_{1bs}$}%
\put(570,185){$t_{1bf}$}%
\put(20,-5){$p_{2s}$}%
\put(120,-5){$p_{2a}$}%
\put(320,-5){$p_{2t}$}%
\put(520,-5){$p_{2b}$}%
\put(620,-5){$p_{2f}$}%
\put(70,-15){$t_{2as}$}%
\put(170,-15){$t_{2af}$}%
\put(270,-15){$t_{2ts}$}%
\put(370,-15){$t_{2tf}$}%
\put(470,-15){$t_{2bs}$}%
\put(570,-15){$t_{2bf}$}%
\put(220,83){$p_{va}$}%
\put(400,83){$p_{vb}$}%
\put(325,60){$t_{mv}$}%
\end{picture}%
}%
\put(220,270){\makebox(0,20){(a)}}%
\put(600,270){\makebox(0,20){(b)}}%
\put(360,0){\makebox(0,20){(c)}}%
\end{picture}
\caption{���Y�V�X�e���̃��f��}
\label{fig:flowshop}
\end{figure}

�����ŁA�@�BA�Ƌ@�BB�����ꂽ�ꏊ�ɂ����āA
�����Ԃŉ^�΂Ȃ���΂Ȃ�Ȃ����̂Ƃ���B
�����Ԃ̃��f����(b)�Ɏ����B
$t_{its}$�A$t_{itf}$ $(i=1,2)$ �͂��ꂼ��A
���i $i$ �̔����J�n�A�I����\���B
$p_{va}$�A$p_{vb}$ �͂��ꂼ��A�����Ԃ��@�BA�AB�̏ꏊ�ɂ��邱�Ƃ�\���B
$t_{mv}$ �͔����Ԃ��@�BB�̏ꏊ����A�̏ꏊ�ֈړ����邱�Ƃ�\���B

2�̃v���[�X $p_{1t}$�A$p_{2t}$ ������Ԃ̃��f��(b)�Œu�������邱�Ƃɂ���āA
�@�B�Ԃ̔������l���������f��(c)�𓾂�B
���̂悤�ɁA����y�g���l�b�g���f����1���邢�͕����̃v���[�X��g�����W�V������
�ʂ̃l�b�g�Œu�������邱�Ƃɂ���āA���ڍׂȃ��f������邱�Ƃ��ł���B
�t�ɁA����y�g���l�b�g�̈ꕔ�����ȒP�ȃl�b�g�Œu�������邱�ƂŁA
��蒊�ۉ����ꂽ���f���𓾂邱�Ƃ��ł���B
\end{example}
%
%\newpage
\begin{example}
�}\ref{fig:printer}�Ƀv�����^�ւ̕�����̏o�͂̃��f���������B
(a)�̓R���s���[�^�̃v�����^����v���O�����A(b)�̓v�����^��\���B
�R���s���[�^�̓v�����^��BUSY�M�����U(0)�ɂȂ�̂�҂��āA�f�[�^�𑗐M����B
�����āA�f�[�^���L���ł��邱�Ƃ��������߂ɁASTROBE�M���𑗂�B
STROBE�M���͕��_���Ȃ̂ŁA�܂��A�M���𗧂�����($1\rightarrow0$)�A
����̎��Ԃ��o�߂�����A�M���𗧂��グ��($0\rightarrow1$)�B
\begin{figure}[htbp]
\centering
\small
\setlength{\unitlength}{0.5pt}
\begin{picture}(680,880)(0,0)
\put(0,500){%
\setlength{\unitlength}{0.5pt}%
\small\tt%
\begin{picture}(360,380)(0,0)%
\thicklines%
\put(140,80){\circle{40}}%
\put(220,80){\circle{40}}%
\put(150,20){\line(1,0){60}}%
\put(140,200){\circle{40}}%
\put(220,200){\circle{40}}%
\put(150,260){\line(1,0){60}}%
\put(60,140){\circle{40}}%
\thinlines%
\put(160,260){\vector(-1,-2){19}}%
\put(200,260){\vector(1,-2){20}}%
\put(140,180){\vector(0,-1){40}}%
\put(140,140){\vector(0,-1){40}}%
\put(220,100){\vector(0,1){40}}%
\put(140,60){\vector(1,-2){20}}%
\put(200,20){\vector(1,2){20}}%
\put(60,10){\vector(0,1){110}}%
\put(180,20){\line(0,-1){10}}%
\put(120,10){\oval(120,20)[b]}%
\thicklines%
\put(280,320){\circle{40}}%
\thinlines%
\put(200,310){\vector(0,-1){50}}%
\put(200,330){\vector(1,0){63}}%
\put(260,310){\oval(120,20)[tl]}%
\put(200,260){\oval(20,140)[tl]}%
\thicklines%
\put(180,360){\circle{40}}%
\thinlines%
\put(180,340){\vector(0,-1){80}}%
\put(160,280){\vector(0,-1){20}}%
\put(110,280){\oval(100,20)[t]}%
\put(60,160){\line(0,1){120}}%
\thicklines%
\put(220,80){\circle*{10}}%
\put(60,140){\circle*{10}}%
\put(280,320){\circle*{10}}%
\put(225,40){STROBE}%
\put(305,300){$\overline{\mbox{BUSY}}$}%
\put(210,160){DATA}%
\put(172,367){\circle*{10}}%
\put(187,367){\circle*{10}}%
\put(174,353){\circle*{10}}%
\put(187,353){\circle*{10}}%
\put(135,40){\makebox(0,0)[br]{$\overline{\mbox{STROBE}}$}}%
\put(35,120){\makebox(0,0)[br]{READY}}%
\put(155,340){\makebox(0,0)[br]{STRING}}%
\put(120,140){\line(1,0){120}}%
\put(250,130){STROBE$\downarrow$}%
\put(215,260){\makebox(0,0)[l]{SEND}}%
\put(215,15){\makebox(0,0)[l]{STROBE$\uparrow$}}%
\end{picture}%
}%
\put(420,500){%
\setlength{\unitlength}{0.5pt}%
\small\tt%
\begin{picture}(260,380)(0,0)%
\thicklines%
\put(40,200){\circle{40}}%
\put(180,200){\circle{40}}%
\put(100,320){\circle{40}}%
\put(180,320){\circle{40}}%
\put(110,380){\line(1,0){60}}%
\put(200,260){\line(-1,0){60}}%
\thinlines%
\put(180,140){\vector(0,1){40}}%
\put(180,220){\vector(0,1){40}}%
\put(180,260){\vector(0,1){40}}%
\put(100,300){\vector(0,-1){160}}%
\put(150,210){\vector(0,1){50}}%
\put(60,210){\oval(180,20)[br]}%
\put(120,380){\vector(-1,-2){19}}%
\put(180,340){\vector(-1,2){19}}%
\put(200,130){STROBE$\downarrow$}%
\thicklines%
\put(100,320){\circle*{10}}%
\put(115,280){$\overline{\mbox{BUSY}}$}%
\put(200,300){PRINTING}%
\put(30,160){DATA}%
\put(175,380){\makebox(0,0)[l]{FINISH}}%
\put(205,260){\makebox(0,0)[l]{START}}%
\put(80,140){\line(1,0){120}}%
\end{picture}%
}%
\put(120,40){%
\setlength{\unitlength}{0.5pt}%
\small\tt%
\begin{picture}(440,380)(0,0)%
\thicklines%
\put(140,80){\circle{40}}%
\put(220,80){\circle{40}}%
\put(150,20){\line(1,0){60}}%
\put(140,200){\circle{40}}%
\put(220,200){\circle{40}}%
\put(150,260){\line(1,0){60}}%
\put(60,140){\circle{40}}%
\thinlines%
\put(160,260){\vector(-1,-2){19}}%
\put(200,260){\vector(1,-2){20}}%
\put(140,180){\vector(0,-1){40}}%
\put(140,140){\vector(0,-1){40}}%
\put(220,100){\vector(0,1){40}}%
\put(140,60){\vector(1,-2){20}}%
\put(200,20){\vector(1,2){20}}%
\put(60,10){\vector(0,1){110}}%
\put(180,20){\line(0,-1){10}}%
\put(120,10){\oval(120,20)[b]}%
\thicklines%
\put(360,200){\circle{40}}%
\put(280,320){\circle{40}}%
\put(360,320){\circle{40}}%
\put(290,380){\line(1,0){60}}%
\put(380,260){\line(-1,0){60}}%
\thinlines%
\put(360,140){\vector(0,1){40}}%
\put(360,220){\vector(0,1){40}}%
\put(360,260){\vector(0,1){40}}%
\put(280,300){\vector(0,-1){160}}%
\put(330,210){\vector(0,1){50}}%
\put(240,210){\oval(180,20)[br]}%
\put(300,380){\vector(-1,-2){19}}%
\put(360,340){\vector(-1,2){19}}%
\put(200,310){\vector(0,-1){50}}%
\put(200,330){\vector(1,0){63}}%
\put(260,310){\oval(120,20)[tl]}%
\put(200,260){\oval(20,140)[tl]}%
\thicklines%
\put(180,360){\circle{40}}%
\thinlines%
\put(180,340){\vector(0,-1){80}}%
\put(160,280){\vector(0,-1){20}}%
\put(110,280){\oval(100,20)[t]}%
\put(60,160){\line(0,1){120}}%
\thicklines%
\put(120,140){\line(1,0){260}}%
\put(380,130){STROBE$\downarrow$}%
\put(220,80){\circle*{10}}%
\put(60,140){\circle*{10}}%
\put(280,320){\circle*{10}}%
\put(225,40){STROBE}%
\put(295,280){$\overline{\mbox{BUSY}}$}%
\put(380,300){PRINTING}%
\put(210,160){DATA}%
\put(172,367){\circle*{10}}%
\put(187,367){\circle*{10}}%
\put(174,353){\circle*{10}}%
\put(187,353){\circle*{10}}%
\put(135,40){\makebox(0,0)[br]{$\overline{\mbox{STROBE}}$}}%
\put(35,120){\makebox(0,0)[br]{READY}}%
\put(155,340){\makebox(0,0)[br]{STRING}}%
\put(215,260){\makebox(0,0)[l]{SEND}}%
\put(215,15){\makebox(0,0)[l]{STROBE$\uparrow$}}%
\put(355,380){\makebox(0,0)[l]{FINISH}}%
\put(385,260){\makebox(0,0)[l]{START}}%
\end{picture}%
}%
\put(0,460){\makebox(360,10){(a)}}%
\put(420,460){\makebox(260,10){(b)}}%
\put(120,0){\makebox(440,10){(c)}}%
\end{picture}
\caption{�v�����^�̃��f��}
\label{fig:printer}
\end{figure}

�v�����^��STROBE�M���̗���������Ńf�[�^����荞�݁ABUSY�M����^(1)�ɂ���B
�����āA�󎚏������s���A���̏I����ABUSY�M�����U�ɂ���B

(a)��(b)�̃l�b�g�ɋ��ʂ̃v���[�X $\overline{\mbox{BUSY}}$�ADATA ��
�g�����W�V���� STROBE$\downarrow$ ��
���ꂼ��d�ˍ��킹�邱�Ƃɂ���āA
�R���s���[�^�Ő��䂳�ꂽ�v�����^�̃��f���𓾂�B
���̂悤�ɁA�����̃y�g���l�b�g�̃v���[�X��g�����W�V�������d�ˍ��킹�āA
�����V�X�e���̃��f������邱�Ƃ��ł���B
\end{example}
\begin{exercise}
�}\ref{fig:vendor}�̃��f�����A50�~�d�݂��󂯕t����悤�ɏC������B
\end{exercise}
%-----------------------------------------------------------------------------
\section{�y�g���l�b�g�̉��}
\subsection{�����I���}
\subsubsection{���Όn��}
�y�g���l�b�g�̂���}�[�L���O $m$ ��
�g�����W�V�����̗� $w=t_{i_1}t_{i_2}\cdots t_{i_r}$ �ɑ΂��āA
$m$ ���� $w$ �̊e�g�����W�V�������������Ή\�ł���Ƃ��A
���Ȃ킿�A
$m[t_{i_1}\rangle m_1$,
$m_1[t_{i_2}\rangle m_2$, $\ldots$,
$m_{r-1}[t_{i_r}\rangle$ �����藧�Ƃ��A
$w$ �� $m$ ����\�Ȕ��Όn��(legal firing sequence)�ł���Ƃ����B
������A$m[w\rangle$ �ƕ\���B���̌��ʂ̃}�[�L���O�� $m'$ �ł���Ƃ��A
$m[w\rangle m'$ �Ə����B
��� $\varepsilon$ (�g�����W�V������1���܂܂Ȃ��u��v)�ɑ΂��āA
$m[\varepsilon\rangle m$ �ł�����̂Ƃ���B
%
\subsubsection{�B�W��}
�y�g���l�b�g $N$ �̏����}�[�L���O $m_0$ ����J�ډ\��
�}�[�L���O�S�̂̏W�����B�W��(reachability set)�Ƃ����A$R(N,\,m_0)$ �Ə����B
�`���I�ɂ́A
$R(N,\,m_0)=\{m\mid \exists w \in T^*;\ m_0[w\rangle m\}$.
�������A$T^*$ �������܂ރg�����W�V�����̗�S�̂̏W���Ƃ���B
\begin{example}
�}\ref{fig:pnexpl1}�̃y�g���l�b�g�̉B�W���́A
$R(N,\,m_0)=\{[k+3\,2\,1\,1]^T$,
$[k\,1\,2\,2]^T$,
$[k\,0\,3\,3]^T$,
$[k\,2\,0\,1]^T$,
$[k\,1\,1\,2]^T$,
$[k\,0\,2\,3]^T$,
$[k\,1\,0\,2]^T$,
$[k\,0\,1\,3]^T$
$\mid k=0,1,2,\ldots\}$
�ł���(�m���߂Ă݂�)�B
\end{example}
%
\subsubsection{�B���}
�y�g���l�b�g $N$ �ƖړI�}�[�L���O $m_f$ ��^�����Ƃ��A
$m_0[w\rangle m_f$ �ƂȂ锭�Όn�� $w$ �����݂��邩�ǂ�����
�B���(reachability problem)�Ƃ����B
�y�g���l�b�g�̐���Ƃ��ẮA
�u���Ή\�ȃg�����W�V�����̔��΂����܂��͋֎~����v
���@����ʓI�ł���B
�B���͂��̐�����@�ɂ����䐫�Ɖ��߂��邱�Ƃ��ł���B
%
\subsubsection{����}
�}�[�L���O $m$ ����B�ȔC�ӂ̃}�[�L���O $m'$ �ɑ΂��āA
�g�����W�V���� $t$ �����Ή\�ȃ}�[�L���O $m''$ �� $m'$ ����B�ł���Ƃ��A
$t$ �� $m$ �Ŋ���(live)�ł���Ƃ����B
���ׂẴg�����W�V�����������}�[�L���O $m_0$ �Ŋ����ł���Ƃ��A
�y�g���l�b�g $N$ �͊����ł���Ƃ����B
�����͒�퓮��̉\���Ɋ֌W���[���B
%
\subsubsection{�L�E��}
���R�� $k$ �ɑ΂��āA
�����}�[�L���O����B�ȔC�ӂ̃}�[�L���O $m$ ��
$m(p)\leq k$ �����藧�Ƃ��A
�v���[�X $p$ �� $k$-�L�E($k$-bounded)�ł���Ƃ����B
1-�L�E�ł��邱�Ƃ���Ɉ��S(safe)�ł���Ƃ����B
�C�ӂ̎��R�� $G$ �ɑ΂��� $m(p)>G$ �Ȃ�}�[�L���O $m$ ���B�ł���Ƃ��A
�v���[�X $p$ �͔�L�E�ł���Ƃ����B

���ׂẴv���[�X�� $k$-�L�E�ł���Ƃ��A
�y�g���l�b�g $N$ �� $k$-�L�E�ł���Ƃ����B

���V�X�e���̃��f���͗L�E�łȂ���΂Ȃ�Ȃ����A
�Ƃ���(2�l)�_���̃��f���͈��S�łȂ���΂Ȃ�Ȃ��B
%
\begin{exercise}
�}\ref{fig:pnexpl1}�̃y�g���l�b�g�ɂ��āA�ȉ��̖₢�ɓ�����B

1. �����}�[�L���O $m_0$ ����A$m_f=[0\,0\,3\,3]^T$ �͉B�ł��邩�B
�����A�B�ł���΁A$m_0[w\rangle m_f$ �ƂȂ锭�Όn�� $w$ ��1�����߂�B

2. �e�g�����W�V�����̊����𔻒肹��B

3. �e�v���[�X�̗L�E���𔻒肹��B
\end{exercise}
%
\subsection{�\���I���}
\subsubsection{�ڑ��s��}
�y�g���l�b�g $N$ �̓��o�͐ڑ��s��(input/output incidence matrix)
$A^-=\{a^-_{ij}\}$�A$A^+=\{a^+_{ij}\}$ ��
�ȉ��ɒ�`����� $|P|\times|T|$ �s��ł���B
\[
a^-_{ij}=\left\{
\begin{array}{ll}
W((p_i,t_j)) & \mbox{if }(p_i, t_j)\in F \\
0 & \mbox{otherwise}
\end{array}\right.
\qquad
a^+_{ij}=\left\{
\begin{array}{ll}
W((t_j,p_i)) & \mbox{if }(t_j,p_i)\in F \\
0 & \mbox{otherwise}
\end{array}\right.
\]
�܂��A$A=A^+-A^-$ ��ڑ��s��Ƃ����B
\begin{example}
�}\ref{fig:pnexpl1}�̃y�g���l�b�g�̐ڑ��s��͈ȉ��̂Ƃ���ł���B
\[
A^-=
\bordermatrix{%
    & t_1 & t_2 & t_3 \cr
p_1 &  3  &  0  &  0  \cr
p_2 &  1  &  0  &  0  \cr
p_3 &  0  &  2  &  0  \cr
p_4 &  0  &  1  &  1  \cr}
\quad
A^+=
\bordermatrix{%
    & t_1 & t_2 & t_3 \cr
p_1 &  0  &  0  &  1  \cr
p_2 &  0  &  1  &  0  \cr
p_3 &  1  &  0  &  0  \cr
p_4 &  1  &  0  &  1  \cr}
\quad
A=
\bordermatrix{%
    & t_1 & t_2 & t_3 \cr
p_1 & -3  &  0  &  1  \cr
p_2 & -1  &  1  &  0  \cr
p_3 &  1  & -2  &  0  \cr
p_4 &  1  & -1  &  0  \cr}
\]
$A$ �ɂ� $p_4$ �� $t_3$ �̊Ԃ̉����A�[�N(�Z���t���[�v, self-loop)��
�\������Ă��Ȃ����Ƃɒ��ӂ���B
\end{example}
$u_j=[0\,\cdots\,0\,\stackrel{(j)}{1}\,0\,\cdots\,0]^T$ �� $t_j$ �ɑ΂���
���΃x�N�g���Ƃ����B
�}�[�L���O $m$ �� $t_j$ �����Ή\�ł��邱�Ƃ́A$A^-u_j\leq m$ �ƕ\�����B
$m[t_j\rangle m'$ �ł���Ƃ��A$m'=m+Au_j$ �ł���B
�}�[�L���O $m$ ���甭�Ή\��
���Όn�� $w=t_{i_1}t_{i_2}\cdots t_{i_r}$ �ɑ΂��āA
$x=\displaystyle\txtsum_{j=1}^{r} u_{i_j}$ �Ƃ���B
$w$ �̔��΂̌��ʂ̃}�[�L���O�� $m'$ �Ƃ���΁A
$m'=m+Ax$ �ł���B$x$ �� $w$ �̔��Ή񐔃x�N�g��(firing count vector)�Ƃ����B
%
\begin{exercise}
������ $m_f=m_0+Ax$ ��p����΁A
�B���͗e�Ղ�%(���Ȃ��Ƃ������v������x�̍����)%
�������Ƃ��ł������ł��邪�A���ۂɂ͂����ł͂Ȃ��B
���̗��R�Ƃ��āA�ǂ�Ȃ��Ƃ��l�����邩�B
\end{exercise}
%
\begin{exercise}
�}\ref{fig:pnexpl3}�̃y�g���l�b�g��
���o�͐ڑ��s�� $A^-$, $A^+$�A����сA�ڑ��s�� $A$ �����߂�B
�܂��A(���o��)�ڑ��s���p����
�}�[�L���O $m_0=[0\,0\,1\,1]^T$ ����A
�g�����W�V���� $t_1$ �����Ή\�ł��邱�Ƃ������A
$w=t_1t_4$ �̔��΂̌��ʂ̃}�[�L���O�����߂�B
\begin{figure}[htb]
\centering
\setlength{\unitlength}{0.5pt}%
\begin{picture}(360,260)(0,0)%
\thicklines%
\put(120,140){\circle{40}}%
\put(240,140){\circle{40}}%
\put(180,190){\line(0,-1){50}}%
\put(180,120){\line(0,-1){50}}%
\put(180,240){\circle{40}}%
\put(40,220){\line(0,-1){60}}%
\put(320,220){\line(0,-1){60}}%
\thinlines%
\put(40,200){\vector(3,1){119}}%
\put(200,240){\vector(3,-1){121}}%
\put(40,180){\vector(3,-2){57}}%
\put(260,140){\vector(3,2){60}}%
\put(180,170){\vector(2,-1){42}}%
\put(180,100){\vector(3,2){42}}%
\put(138,150){\vector(2,1){42}}%
\put(134,125){\vector(2,-1){46}}%
\thicklines%
\put(180,30){\circle{40}}%
\thinlines%
\put(350,30){\vector(-1,0){150}}%
\put(10,190){\vector(1,0){30}}%
\put(10,30){\line(1,0){150}}%
\put(350,190){\line(-1,0){30}}%
\put(10,110){\oval(20,160)[l]}%
\put(350,110){\oval(20,160)[r]}%
\put(180,30){\circle*{10}}%
\put(240,140){\circle*{10}}%
\put(100,110){$p_2$}%
\put(250,110){$p_3$}%
\put(190,0){$p_4$}%
\put(190,210){$p_1$}%
\put(185,185){$t_2$}%
\put(186,66){$t_3$}%
\put(324,216){$t_4$}%
\put(45,216){$t_1$}%
\end{picture}%
\caption{�y�g���l�b�g}
\label{fig:pnexpl3}
\end{figure}
\end{exercise}
%
\subsubsection{T�C���o���A���g}
����}�[�L���O $m$ ���甭�Ή\��
���łȂ����Όn�� $w$ �̔��΂̌��ʂ̃}�[�L���O���ӂ����� $m$ �ł���Ƃ���B
$w$ �̔��Ή񐔃x�N�g���� $x$ �Ƃ���΁A
$m=m+Ax$ ���A$Ax=0$ �����藧�B
������ $Ax=0$ �̔񕉐����� $x$ ��T�C���o���A���g(T-invariant)�Ƃ����B
%
\subsubsection{S�C���o���A���g}
�e�v���[�X $p_j$ �ɔ񕉐����̏d�� $y_j$ ���l����B
$y^Tm$ �̓g�[�N���̏d�ݕt���a�ł���B
�����A$y^TA=0$ �����藧�Ȃ�΁A
$m_0$ ����B�ȔC�ӂ̃}�[�L���O $m$ �ɑ΂��āA
$y^Tm=y^T(m_0+Ax)=y^Tm_0+(y^TA)x=y^Tm_0$ ���A
�d�ݕt���a�͕s�ςł���B
������ $A^Ty=0$ �̔񕉐����� $y$ ��S�C���o���A���g(S-invariant)���邢�́A
P�C���o���A���g�Ƃ����B
%
\begin{exercise}
�}\ref{fig:pnexpl3}�̃y�g���l�b�g��T�C���o���A���g�AS�C���o���A���g�����߂�B
\end{exercise}
\section{�y�g���l�b�g�̃T�u�N���X}
�y�g���l�b�g�̍\���ɐ�����������T�u�N���X���e���Ă���Ă���B
�y�g���l�b�g�̋����I��͖��͈�ʓI�ɉ������Ƃ�������A
�T�u�N���X�ɂ���ẮA�����̖�肪�����悭������ꍇ������B
\subsection{�}�[�N�O���t}
�e�v���[�X�̓��o�̓g�����W�V���������傤��1���ł���y�g���l�b�g��
�}�[�N�O���t(marked graph)�Ƃ����B
�}�[�N�O���t�͋�����\�����Ƃ��ł��Ȃ��B
%
\subsection{��ԋ@�B}
�e�g�����W�V�����̂̓��o�̓v���[�X�����傤��1���ł���y�g���l�b�g��
��ԋ@�B(state machine)�Ƃ����B
��ԋ@�B�͓�����\�����Ƃ��ł��Ȃ��B
%
\subsection{���R�I���l�b�g}
�v���[�X $p$ ���� �g�����W�V���� $t$ �֌������A�[�N�́A
$p$ �̗B��̏o�̓A�[�N�ł���(�}\ref{fig:fc}(a))���A
$t$ �̗B��̓��̓A�[�N�ł���(�}\ref{fig:fc}(b))����
�����ꂩ�ł���y�g���l�b�g�����R�I���l�b�g(free choice net)�Ƃ����B
���R�I���l�b�g�ł́A���ʂ̓��̓v���[�X�����g�����W�V������
���ׂĂ����Ή\�ł��邩�A���ׂĂ����Ή\�łȂ����̂����ꂩ�ł���B
\begin{figure}[htb]
\centering
\setlength{\unitlength}{0.5pt}%
\begin{picture}(360,100)(0,20)%
\thicklines%
\put(20,100){\circle{40}}%
\put(80,100){\circle{40}}%
\put(140,100){\circle{40}}%
\put(50,40){\line(1,0){60}}%
\thinlines%
\put(80,80){\vector(0,-1){40}}%
\put(127,83){\vector(-2,-3){28}}%
\put(31,83){\vector(2,-3){29}}%
\thicklines%
\put(280,100){\circle{40}}%
\put(260,40){\line(1,0){40}}%
\put(320,40){\line(1,0){40}}%
\put(240,40){\line(-1,0){40}}%
\thinlines%
\put(280,80){\vector(0,-1){40}}%
\put(294,86){\vector(1,-1){45}}%
\put(265,86){\vector(-1,-1){45}}%
\put(80,20){\makebox(0,0){(a)}}%
\put(280,20){\makebox(0,0){(b)}}%
\end{picture}%
\caption{���R�I���l�b�g}
\label{fig:fc}
\end{figure}
\begin{exercise}
�}\ref{fig:subclass}(a)(b)(c)(d)�̃l�b�g�́A�}�[�N�O���t�A��ԋ@�B�A
���R�I���l�b�g�A���̑��̂�����ł��邩�B
\begin{figure}[htb]
\centering
\setlength{\unitlength}{0.5pt}
\begin{picture}(740,420)
\put(20,240){%
\begin{picture}(300,180)(0,0)%
\thicklines%
\put(30,150){\line(0,-1){60}}%
\put(90,150){\circle{40}}%
\put(90,90){\circle{40}}%
\put(150,130){\line(0,1){50}}%
\put(150,110){\line(0,-1){50}}%
\put(210,150){\circle{40}}%
\put(210,90){\circle{40}}%
\put(270,150){\line(0,-1){60}}%
\put(150,20){\circle{40}}%
\thinlines%
\put(30,130){\vector(2,1){40}}%
\put(30,110){\vector(2,-1){40}}%
\put(110,150){\vector(1,0){40}}%
\put(150,150){\vector(1,0){40}}%
\put(230,150){\vector(2,-1){40}}%
\put(110,90){\vector(1,0){40}}%
\put(150,90){\vector(1,0){40}}%
\put(230,90){\vector(2,1){40}}%
\put(290,20){\vector(-1,0){120}}%
\put(10,120){\vector(1,0){20}}%
\put(10,20){\line(1,0){120}}%
\put(290,120){\line(-1,0){20}}%
\put(290,70){\oval(20,100)[r]}%
\put(10,70){\oval(20,100)[l]}%
\end{picture}%
}%
\put(420,240){%
\setlength{\unitlength}{0.5pt}%
\begin{picture}(300,180)(0,0)%
\thicklines%
\put(30,150){\line(0,-1){60}}%
\put(90,150){\circle{40}}%
\put(90,90){\circle{40}}%
\put(150,130){\line(0,1){50}}%
\put(150,110){\line(0,-1){50}}%
\put(210,150){\circle{40}}%
\put(210,90){\circle{40}}%
\put(270,150){\line(0,-1){60}}%
\put(150,20){\circle{40}}%
\thinlines%
\put(30,130){\vector(2,1){40}}%
\put(30,110){\vector(2,-1){40}}%
\put(110,150){\vector(1,0){40}}%
\put(150,150){\vector(1,0){40}}%
\put(230,150){\vector(2,-1){40}}%
\put(110,90){\vector(1,0){40}}%
\put(150,90){\vector(1,0){40}}%
\put(230,90){\vector(2,1){40}}%
\put(290,20){\vector(-1,0){120}}%
\put(10,120){\vector(1,0){20}}%
\put(10,20){\line(1,0){120}}%
\put(290,120){\line(-1,0){20}}%
\put(290,70){\oval(20,100)[r]}%
\put(10,70){\oval(20,100)[l]}%
\put(107,138){\vector(4,-3){41}}%
\end{picture}%
}%
\put(0,20){%
\setlength{\unitlength}{0.5pt}%
\begin{picture}(340,190)(0,0)%
\thicklines%
\put(50,130){\circle{40}}%
\put(110,140){\line(0,1){50}}%
\put(110,120){\line(0,-1){50}}%
\put(170,160){\circle{40}}%
\put(170,100){\circle{40}}%
\put(290,130){\circle{40}}%
\put(170,60){\line(0,-1){60}}%
\thinlines%
\put(110,160){\vector(1,0){40}}%
\put(110,100){\vector(1,0){40}}%
\put(68,139){\vector(2,1){42}}%
\put(68,120){\vector(2,-1){42}}%
\put(330,30){\vector(-1,0){160}}%
\put(10,130){\vector(1,0){20}}%
\put(10,30){\line(1,0){170}}%
\put(330,130){\line(-1,0){20}}%
\put(10,80){\oval(20,100)[l]}%
\put(330,80){\oval(20,100)[r]}%
\thicklines%
\put(230,160){\line(0,-1){60}}%
\thinlines%
\put(190,160){\vector(2,-1){40}}%
\put(190,100){\vector(2,1){40}}%
\put(230,130){\vector(1,0){40}}%
\end{picture}%
}%
\put(400,20){%
\setlength{\unitlength}{0.5pt}%
\begin{picture}(340,190)(0,0)%
\thicklines%
\put(50,130){\circle{40}}%
\put(110,140){\line(0,1){50}}%
\put(110,120){\line(0,-1){50}}%
\put(170,160){\circle{40}}%
\put(170,100){\circle{40}}%
\put(230,190){\line(0,-1){50}}%
\put(230,120){\line(0,-1){50}}%
\put(290,130){\circle{40}}%
\put(170,60){\line(0,-1){60}}%
\thinlines%
\put(110,160){\vector(1,0){40}}%
\put(190,160){\vector(1,0){40}}%
\put(230,160){\vector(2,-1){43}}%
\put(110,100){\vector(1,0){40}}%
\put(190,100){\vector(1,0){40}}%
\put(230,100){\vector(2,1){41}}%
\put(68,139){\vector(2,1){42}}%
\put(68,120){\vector(2,-1){42}}%
\put(330,30){\vector(-1,0){160}}%
\put(10,130){\vector(1,0){20}}%
\put(10,30){\line(1,0){170}}%
\put(330,130){\line(-1,0){20}}%
\put(10,80){\oval(20,100)[l]}%
\put(330,80){\oval(20,100)[r]}%
\end{picture}%
}%
\put(20,220){\makebox(300,10){(a)}}
\put(420,220){\makebox(300,10){(b)}}
\put(0,0){\makebox(340,10){(c)}}
\put(400,0){\makebox(340,10){(d)}}
\end{picture}
\caption{�T�u�N���X}
\label{fig:subclass}
\end{figure}
\end{exercise}

\section{�Q�l����}
\begin{enumerate}
\item J.~L.~Peterson ���A�s��E���� ��A�y�g���l�b�g����A�����o�� (1984)\\
``Petri Net Theory and the Modeling of Systems (Prentice-Hall 1981)''
�̖M��B
\item W.~Reisig ���A���J��E���� ��A�y�g���l�b�g���_����A
�V���v�����K�[�E�t�F�A���[�N���� (1988)\\
``Petri Nets (Springer-Verlag 1985)'' �̖M��B
\item �v����������w��U���ۃV�X�e���������ψ���ҁA
�y�g���l�b�g�Ƃ��̉��p�A�v����������w�� (1992)
\item ���c ���v�A�y�g���l�b�g�̉�͂Ɖ��p�A�ߑ�Ȋw�� (1992)
\item �Œ� �v�Y�A����y�g���l�b�g�A�R���i�� (1992)
\end{enumerate}
%-----------------------------------------------------------------------------
%\clearpage
\appendix
\section{��藪��}
\begin{answer}
�Ⴆ�΁A�R���s���[�^�A�]�A
�ʐM�v���g�R���A��Ԃ̉^�s�A�i�ׁA
���w����(���q���ɒ��ڂ����ꍇ)�ȂǁB
\end{answer}
\begin{answer}�@

1. $t_1$ �� $t_3$ �� $t_4$

2. $t_1$ �̔��΂̌��ʂ� $[1\,2\,1\,0]^T$�A
$t_3$ �̔��΂̌��ʂ� $[2\,4\,0\,2]^T$�A
$t_4$ �̔��΂̌��ʂ� $[3\,0\,1\,0]^T$�B

3. $t_1$ �� $t_4$
\end{answer}
\begin{answer}
�Ⴆ�΁A�}\ref{fig:vendor2}�̃y�g���l�b�g�B
\begin{figure}[htb]
\small
\centering
\setlength{\unitlength}{0.5pt}%
%\newcommand{\yen}{\makebox[0pt][l]{=}Y}%
\small%
\begin{picture}(580,380)(0,0)%
\thicklines%
\put(69,240){\line(1,0){50}}%
\put(139,240){\line(1,0){50}}%
\put(209,240){\line(1,0){50}}%
\put(279,240){\line(1,0){50}}%
\put(349,240){\line(1,0){50}}%
\put(419,240){\line(1,0){50}}%
\put(519,200){\circle{40}}%
\thinlines%
\put(259,200){\vector(1,0){240}}%
\put(399,210){\vector(1,0){101}}%
\put(119,190){\vector(1,0){382}}%
\put(328,205){\vector(1,0){172}}%
\put(468,215){\vector(1,0){36}}%
\put(189,195){\vector(1,0){311}}%
\put(48,185){\vector(1,0){456}}%
\put(469,240){\oval(20,50)[bl]}%
\put(399,240){\oval(20,60)[bl]}%
\put(329,240){\oval(20,70)[bl]}%
\put(259,240){\oval(20,80)[bl]}%
\put(119,240){\oval(20,100)[bl]}%
\put(49,240){\oval(20,110)[bl]}%
\thicklines%
\put(449,130){\circle{40}}%
\put(339,130){\circle{40}}%
\put(129,130){\circle{40}}%
\thinlines%
\put(449,240){\vector(0,-1){90}}%
\put(299,240){\vector(1,-3){31}}%
\put(379,240){\vector(-1,-3){30}}%
\put(89,240){\vector(1,-3){31}}%
\put(169,240){\vector(-1,-3){30}}%
%\put(19,240){\vector(1,-1){96}}%
\put(20,240){\oval(20,220)[bl]}%
\put(20,130){\vector(1,0){90}}%
\put(189,240){\oval(20,90)[bl]}%
\put(239,240){\vector(-1,-1){95}}%
\thicklines%
\put(159,320){\circle{40}}%
\put(279,320){\circle{40}}%
\put(399,320){\circle{40}}%
\thinlines%
\put(383,309){\vector(-2,-1){133}}%
\put(414,308){\vector(1,-2){34}}%
\put(394,300){\vector(-1,-3){19}}%
\put(292,306){\vector(1,-1){64}}%
\put(283,300){\vector(1,-3){20}}%
\put(258,319){\vector(-2,-1){156}}%
\put(263,307){\vector(-4,-3){88}}%
\put(159,300){\vector(0,-1){60}}%
\put(173,307){\vector(1,-1){67}}%
\put(145,306){\vector(-1,-1){66}}%
\put(139,320){\vector(-3,-2){119}}%
\thicklines%
\put(129,380){\line(1,0){60}}%
\put(249,380){\line(1,0){60}}%
\put(369,380){\line(1,0){60}}%
\put(519,130){\circle{40}}%
\put(509,380){\line(1,0){60}}%
\thinlines%
\put(519,220){\vector(0,1){160}}%
\put(549,130){\vector(-1,0){10}}%
\put(549,380){\oval(20,500)[br]}%
\put(159,380){\vector(0,-1){40}}%
\put(279,380){\vector(0,-1){40}}%
\put(399,380){\vector(0,-1){40}}%
\thicklines%
\put(99,70){\line(1,0){60}}%
\put(309,70){\line(1,0){60}}%
\put(419,70){\line(1,0){60}}%
\thinlines%
\put(129,110){\vector(0,-1){40}}%
\put(339,110){\vector(0,-1){40}}%
\put(449,110){\vector(0,-1){40}}%
\put(149,80){\vector(0,-1){10}}%
\put(359,80){\vector(0,-1){10}}%
\put(159,80){\oval(20,40)[tl]}%
\put(369,80){\oval(20,28)[tl]}%
\put(479,80){\oval(20,20)[tl]}%
\put(469,80){\vector(0,-1){10}}%
\put(159,110){\oval(700,20)[br]}%
\put(368,104){\oval(302,20)[br]}%
\put(479,100){\oval(100,20)[br]}%
\put(519,110){\line(0,-1){10}}%
\put(529,112){\line(0,-1){15}}%
\put(509,112){\line(0,-1){5}}%
\thicklines%
\put(0,240){\line(1,0){50}}%
\put(340,10){\circle{40}}%
\put(450,10){\circle{40}}%
\put(230,10){\circle{40}}%
\thinlines%
\put(440,70){\vector(-4,-1){192}}%
\put(320,70){\vector(-2,-1){82}}%
\put(130,70){\vector(2,-1){86}}%
\put(450,70){\vector(-2,-1){93}}%
\put(340,70){\vector(0,-1){40}}%
\put(458,70){\vector(0,-1){42}}%
\put(58,280){11}%
\put(108,280){6}%
\put(232,270){2}%
\put(278,270){3}%
\put(440,270){2}%
\put(328,53){4}%
\put(400,30){4}%
\put(60,110){\yen 110}%
\put(270,110){\yen 150}%
\put(380,110){\yen 200}%
\put(160,-10){juice}%
\put(280,-10){\yen 10}%
\put(390,-10){\yen 50}%
\put(100,360){\yen 10}%
\put(220,360){\yen 50}%
\put(340,360){\yen 100}%
\put(450,360){button}%
\end{picture}%
\caption{�����̔��@�̃��f��2}
\label{fig:vendor2}
\end{figure}
\end{answer}
\begin{answer}�@

1. �B�ł���B$m_0$ ���� $m_f$ �ɑJ�ڂ��锭�Όn��́A
$t_3t_3t_3t_1t_1$�A
$t_3t_3t_1t_3t_1$�A
$t_3t_1t_3t_3t_1$�A
$t_1t_3t_3t_3t_1$ �̂����ꂩ�B

2. $t_1$�A$t_2$ �͊����łȂ��B
$m_0$ ����B�ȃ}�[�L���O $m_d=[0\,0\,1\,3]^T$ ����B�ȃ}�[�L���O��
$t_1$�A$t_2$ �����΂ł�����̂͑��݂��Ȃ��B
$t_3$ �͊����ł���B$p_4$ �̃}�[�L���O�͂�������0�ɂȂ�Ȃ��B

3. $p_1$ �͔�L�E�A$p_2$ ��2�L�E�A$p_3$�A$p_4$ ��3�L�E�ł���B
\end{answer}
\begin{answer}
���Ή\�̂��߂̏������l������Ă��Ȃ����ƁA
���Ή񐔃x�N�g���͔��΂̏������l�����Ă��Ȃ����Ƃɂ��B
\end{answer}
\begin{answer}
�ڑ��s��͈ȉ��̂Ƃ���B
\[
A^-=
\left[
\begin{array}{cccc}
0 & 0 & 0 & 1 \\
0 & 1 & 1 & 0 \\
0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0
\end{array}\right]
\ 
A^+=
\left[
\begin{array}{cccc}
1 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 \\
0 & 0 & 0 & 1
\end{array}\right]
\ 
A=
\left[
\begin{array}{cccc}
 1 &  0 &  0 & -1 \\
 1 & -1 & -1 &  0 \\
 0 &  1 &  1 & -1 \\
-1 &  0 &  0 &  1
\end{array}\right]
\]
$t_1$ �����Ή\�ł��邽�߂̏����́A
\[
A^- u_1 = 
\left[
\begin{array}{cccc}
0 & 0 & 0 & 1 \\
0 & 1 & 1 & 0 \\
0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0
\end{array}\right]
\left[
\begin{array}{c}
1 \\
0 \\
0 \\
0 \end{array}\right]
=
\left[
\begin{array}{c}
0 \\
0 \\
0 \\
1 \end{array}\right]
\leq
\left[
\begin{array}{c}
0 \\
0 \\
1 \\
1 \end{array}\right]
(=m_0)
\]
���A��������Ă���B$w=t_1t_4$ �̔��΂̌��ʂ̃}�[�L���O�� $m$ �Ƃ���΁A
\begin{eqnarray*}
m&=&m_0+A(u_1+u_4)=
\left[
\begin{array}{c}
0 \\
0 \\
1 \\
1 \end{array}\right]
+
\left[
\begin{array}{cccc}
 1 &  0 &  0 & -1 \\
 1 & -1 & -1 &  0 \\
 0 &  1 &  1 & -1 \\
-1 &  0 &  0 &  1
\end{array}\right]
\left[
\begin{array}{c}
1 \\
0 \\
0 \\
1 \end{array}\right]\\
&=&
\left[
\begin{array}{c}
0 \\
0 \\
1 \\
1 \end{array}\right]
+
\left[
\begin{array}{c}
0 \\
1 \\
-1 \\
0 \end{array}\right]\\
&=&
\left[
\begin{array}{c}
0 \\
1 \\
0 \\
1 \end{array}\right]
\end{eqnarray*}
\end{answer}
\begin{answer}
$x_1=[1\,1\,0\,1]^T$�A$x_2=[1\,0\,1\,1]^T$ �Ƃ��āA
T�C���o���A���g�́A
$x=a_1x_1+a_2x_2$ ($a_1\geq 0$, $a_2\geq 0$)�ŕ\�����C�ӂ̃x�N�g���B
$y_1=[1\,0\,0\,1]^T$�A$y_2=[0\,1\,1\,1]^T$ �Ƃ��āA
S�C���o���A���g�́A
$y=b_1y_1+b_2y_2$ ($b_1\geq 0$, $b_2\geq 0$)�ŕ\�����C�ӂ̃x�N�g���B
\end{answer}
\begin{answer}
(a)�}�[�N�O���t(���R�I���l�b�g�ł�����)�A
(b)�}�[�N�O���t�A��ԋ@�B�A���R�I���l�b�g�̂�����ł��Ȃ��A
(c)���R�I���l�b�g�A(d)��ԋ@�B(���R�I���l�b�g�ł�����)
\end{answer}
\end{document}
