\documentclass[12pt]{article}
%% newest 10/26
\usepackage{amsmath}
\usepackage{amssymb}

\usepackage{color}
\usepackage{graphicx}
\usepackage{epstopdf} 
\DeclareGraphicsExtensions{.pdf,.eps,.png,.jpg,.mps} 

\textheight 230mm
\topmargin 5mm
\textwidth 160mm
\oddsidemargin -2mm

\pagestyle{myheadings}
\markright{(Automaton and its application)}

\newtheorem{formula}{Rule}
\newtheorem{example}{Example}
\newtheorem{exercise}{Exercise}
\newtheorem{algorithm}{Algorithm}
\newtheorem{definition}{Definition}


\makeatletter
\let\c@figure\c@table
\let\p@figure\p@table
\let\cl@figure\cl@table
\let\thefigure\thetable
\makeatother


\begin{document}
\thispagestyle{empty}

\title{{\bf Automaton and its Application} \\ 
        {\large Lecture notes for special course in 2012 \\
\author{Akira Imada \\
Brest State Technical University, Belarus \\
        \hspace*{1in}\\
        \hspace*{1in}\\
        (last modified on)}}}
\maketitle

\clearpage
\section{Introduction}
The most important keyword throughout this lecture is {\it "state."} Our behavior when we see or something is dependent on our state of mind. For example, our behavior in meeting our friend when we are in a happy state of mind would be different than when we are in a unhappy state of mind. In computational scenario, ...


\section{Conway's Game of Life}
In 1970 John Conway devised a zero-player game called the Game of Life\footnote{The first successfully mass marketed personal computer was the Commodore PET introduced in January 1977.}. The universe is toroidal 2-D grid. Each cell has either one of two states. We may call the two states, say, dead and alive. The state is determined by the following rules.
\color{red}
\begin{formula}[Classification only with prior probability] \label{rule-1}
\hspace{.1in}
\begin{itemize}
\setlength{\itemsep}{0pt}
\item[1.] Any live cell will die if its live neighbors are fewer than two (too lonely to live).
\item[2.] Any live cell will remain live if its live neighbors are two or three.
\item[3.] Any live cell will die if its live neighbors are more than three (too crowdy to live).
\item[4.] Any dead cell will become a live cell only if its live neighbors are exactly three, otherwise remain die.
\end{itemize}
\end{formula}
\color{black}
Note that the number of live neighbors is based on the cells before the rule was applied.


\begin{figure}[h]
 \begin{center}
\includegraphics[width=2cm,height=2cm]{life-one.eps}
 \end{center}
 \caption{What do you think the fate of this center point?}
\end{figure}


\clearpage
\noindent
{\bf Examples of pattern to start with.}\\
The game is zero-player in which we create an initial configuration and observe how the initial configuration evolves. Now let's see typical initial configuration.
\begin{figure}[h]
 \begin{center}
\includegraphics[width=2cm,height=2cm]{life-block.eps}
\includegraphics[width=2cm,height=2cm]{life-blinker.eps}
\includegraphics[width=2cm,height=2cm]{life-glider.eps}
\includegraphics[width=2cm,height=2cm]{life-pulser.eps}
 \end{center}
 \caption{Examples of simple patterns to start with.}
\end{figure}


\begin{figure}[h]
 \begin{center}
\includegraphics[width=2cm,height=2cm]{life-queenbee.eps}
 \end{center}
 \caption{Initial configuration of Queenbee.}
\end{figure}

\clearpage
\section{Cell Automaton (CA)}
Universe is any dimension of grid. Each cell in the grid take one state out of $k$ different state. We represent those states by number $1,2,3,\cdots,k$, $k$ different clour like {\it white, black, blue, red, $\cdots$}, or by using a daily language, like {\it happy, unhappy, angry, $\cdots$}. These distinct states are determined being affected by states of neighbor cell of each cell.

\subsection{The Simplest Nontrivial 1-D CA}
Each cell has a state either zero or one, or equivalently. {\it white} and {\it black}.
The state of a cell a determined by the state of the two nearest neighbor cell of right and left and itself.
For example: 
\color{blue}
\begin{quote}
{\it The cell of state '1' whose right cell is state '0' and left cell is state '1' at time $t$ becomes '1' at time $t+1$.}
\end{quote}
\color{black}
Let's describe this by
\begin{center}
(0 1 1) $\rightarrow$ 1.
\end{center}
Note that we need $2^3=8$ such lines in order to specify all cases. Hence, there are 256 such rules. Each of the 256 rules is indexed by a binary number whose decimal representation is given to the rule as its name.

\subsubsection{Rule 30}

\color{blue}
\begin{exercise}
Apply the Rule 30 starting with a single black cell. Then display those evolved cells from $t=0$ to $t=20$.
\end{exercise}
\color{black}

\subsubsection{Rule 110}

\color{blue}
\begin{exercise}
What about Rule 110?
\end{exercise}
\color{black}

\subsubsection{Application}
It's easy to imagine we can apply, say Rule 30, to cryptography


\subsection{Two dimensional cell automaton}
For the sake of simplicity we assume only two possible states here, say black and white. Also assume each cell concerns only the states of eight its nearest cells and the state of itself. There are $2^9=512$ possible configuration. For each of these 512 patterns at time $t$, The rule specifies the state of the center cell at time $t+1$ The game of life by Conway is one of them.


\clearpage
\section{Finite State Automaton (FSA)}
Finite State Automaton (FSA) is made up of a number of states such as cell automaton. But states are not affected by other states but affected by input. Then the state output an action and transfer to the other state (including itself). 

\begin{figure}[hbtp]
\begin{center}
   \includegraphics[width=5cm,height=3cm]{fsa.eps}
   \includegraphics[width=9cm,height=3cm]{fsa-2.eps}
\end{center}
\end{figure}

\clearpage
\noindent
The behavior of a FSA is defined by a transition table such as the below. In this example, the FSA has 8 states (A, B, C, D, E, F, G, and H) of which A is the initial state. The number of inputs is two (0 and 1) and the number of actions is four (a, b, c, and d).

\begin{small}
\begin{table}[h]
\begin{center}
\begin{tabular}{c c c c} \hline \hline
current state & input  &  action & next state \\ \hline
A             & 0      &  a      & B          \\
\hspace{.1in} & 1      &  c      & H          \\ \hline
B             & 0      &  d      & C          \\
\hspace{.1in} & 1      &  b      & G          \\ \hline
C             & 0      &  c      & D          \\
\hspace{.1in} & 1      &  a      & B          \\ \hline
D             & 0      &  d      & E          \\
\hspace{.1in} & 1      &  a      & D          \\ \hline
E             & 0      &  c      & F          \\
\hspace{.1in} & 1      &  a      & C          \\ \hline
F             & 0      &  d      & F          \\
\hspace{.1in} & 1      &  a      & D          \\ \hline
G             & 0      &  a      & H          \\
\hspace{.1in} & 1      &  b      & F          \\ \hline
H             & 0      &  c      & F          \\
\hspace{.1in} & 1      &  a      & B          \\ \hline \hline
\end{tabular}
\caption{An example of transition table of FSA with 8 states 2 inputs, 4 actions}
\end{center}
\end{table}
\end{small}

\noindent
The schematic diagram of this automaton is shown in Figure 5. 

\begin{figure}[hbtp]
\begin{center}
\rotatebox[origin=c]{270}{
   \includegraphics[width=4cm,height=5cm]{fsa-0.eps}}
\caption{A schematic diagram of the FSA of the above transition table.}
\end{center}
\end{figure}

\clearpage 
\subsection{How to design FSA?}
We have to determine, (i) initial state to start with, (ii) how many states it has, (iii) which inputs will be given, (iv) how many actions it will make. Then for each of the states it should be specified, which action it will take on which input and which state it will transfer. That is to say, the 3rd column and the 4th column above should be specified by the designer. Note that the 1st and the 2nd is automatic depending on how many states and how many inputs.\\




\clearpage
\subsection{A toy application of FSA}
Now let's make an artificial ant explore an gridworld.
\begin{figure}[hbtp]
\begin{center}
   \includegraphics[width=3cm,height=1.5cm]{ant.eps}
\end{center}
\end{figure}
\noindent
A strange assumption but there is one grain of sugar, say 1mg, in the dark cell while nothing in the white cells. Now an ant explores the grid starting from the entrance with the aim of eating all those grains by following the shortest path to the last grain of sugar, that is to say, with 98 steps. Try to specify the transition table for such an FSA.
\begin{figure}[hbtp]
\begin{center}
   \includegraphics[width=9cm,height=9cm]{john-muir-trail-2.eps}
\caption{John-muir-trail. An agent should follow the path shown with shaded cell as effectively as possible. Note that the grid has a toroidal structure (the left neighbor cell of the leftmost cell is the rightmost cell).}
\end{center}
\end{figure}


\noindent
Generally speaking, in order for an FSA to make a meaningful behavior, it will not easy to specify a transition table. In this example, it would be interesting to make it using Genetic Algorithm. For the purpose, let's represent the transition table by all binary numbers. For the above example, the binary version of the transition table mentioned above is shown in Table 2.\\
\begin{table}[h]
\begin{center}
\begin{tabular}{c c c c} \hline \hline
current state  & input  &  action & next state \\ \hline
000            & 0      &  00     & 001        \\
\hspace{.1in}  & 1      &  10     & 110        \\
001            & 0      &  11     & 010        \\
\hspace{.1in}  & 1      &  01     & 110        \\
010            & 0      &  10     & 011        \\
\hspace{.1in}  & 1      &  00     & 001        \\
011            & 0      &  11     & 100        \\
\hspace{.1in}  & 1      &  00     & 011        \\
100            & 0      &  10     & 101        \\
\hspace{.1in}  & 1      &  00     & 010        \\
101            & 0      &  11     & 101        \\
\hspace{.1in}  & 1      &  00     & 011        \\
110            & 0      &  00     & 110        \\
\hspace{.1in}  & 1      &  01     & 101        \\
111            & 0      &  10     & 101        \\
\hspace{.1in}  & 1      &  00     & 001        \\ \hline \hline
\end{tabular}
\caption{A binary version of the above mentioned transition table.}
\end{center}
\end{table}


\noindent
Now we express this specific FSA with a chromosome
\begin{tiny}\begin{displaymath}
00001101101101001110100110000111100000111010100010111010001100110011011010100001
\end{displaymath}\end{tiny}
\noindent
Now you may notice the number of states and the number of action is better to be in the form of $2^n$.\\

\noindent
We are now ready to apply a Genetic Algorithm to evolve random FSA to be cleaver enough to solve this John-muir-trail by the following procedure.

\begin{itemize}
\setlength{\itemsep}{0pt}
\item[1.] Create a population of, say 100, random binary chromosome whose length is 80.
\item[2.] Make it try the trail one by one and evaluate how many sugar it can collect (fitness).
\item[3.] Select two chromosome as parents (by, e.g., Roulette wheel selection) and create on child by crossover and mutation.
\item[4.] repeat 3. (say, 100 times) untill we create a new generation.
\item[5.] repeat 3. and 4. untill we find a perfect chromosome.
\end{itemize}



\clearpage
\subsection{Different version of Finite state automaton: Accept input series or reject?}
Now we are proceeding to yet another version of FSA. We don't specify action for each input, but instead, we assign each state final one or not final one. If the state is one of those final states when all inputs are given, then FSA say the series of input is {\it accepted}, otherwise {\it rejected}.

In other words, we give a specific status to some states if a series of state transition by a series of inputs ends at one of these states, the series of inputs is accepted as legal. We don't need to specify {\it actions} any more when a state shifts to another state. This is an FSA to check a series of inputs is accept or not, not for produce a series of actions.

\subsubsection{A toy examples - Vending machine for Coke}
Now as a toy example, let's design an FSA for vending machine for coke. (i) As a first scenario, we assume we have only 10 yen coins, while one coke costs 110 yen; (ii) the second one is a little more complicated. Assume we have 2 distinct coins of 10, 100 yen while cole is till 110 yen.\\

\noindent
We may think a more complicated one by adding Santa whose price is 80 yen, and/or we have yet another coins of 500 yen. Further, how could we design an USA which give back a return. For example, some one put a 500 yen coin to buy cola, expecting a return of coins for 390 yen. But let me skip these examples.

\begin{figure}[hbtp]
\begin{center}
   \includegraphics[width=6cm,height=5cm]{vending-1.eps}
   \includegraphics[width=6cm,height=5cm]{vending-2.eps}
\caption{Left: FSA accept only 10 yen coins. Right: FSA accept both 10 yen coins and 100 yen coins. Both for 110 yen cola.}
\end{center}
\end{figure}


\subsubsection{A language recognition by FSA}
Again directed graph where nodes denote states, arc from the source state to the target state labeled with a symbol from an alphabet. As before, in the diagram the initial state is shown with a short arrow that points to it from nowhere. The final states are represented as two concentric circles.\\

\noindent
We now take a look at Figure~\ref{Fig:lang-1}. It contains 5 states (A, B, C, D, and E) of which A is the initial state, and C and D are the final states, and the alphabet is made up 6 symbols (a, b, c, d, e, and f). The FSA processes a sequence of input symbols. In each state, it checks if the next input symbol matches any of the labels on the arc that goes out from the state. If so, the state move to this target state. In case of no such transition the FSA stops and rejects the input. The input is accepted when all inputs are read\footnote{one method to give the end of sequence might be a carriage-return.} and the FSA is in a final State.\\

\begin{figure}[hbtp]
\begin{center}
   \includegraphics[width=8cm,height=4cm]{fsa-lang-11.eps}
\caption{An example FSA to accept a language.}
\label{Fig:lang-1}
\end{center}
\end{figure}

\noindent
A set of all the possible sequences which can be accepted by the FSA is called the {\it language} accepted by the FSA. For example, ${b, ac, acc, accd, accdc, ..., accef, ...}$ is a language accepted by the FSA shown in Figure~\ref{Fig:lang-1}. \\

\noindent
A state X is said to be reachable from another state Y if and only if there is a sequence of transitions leading the state X from the state Y. An FSA is said to be start-useful if and only if every state is reachable from the initial state. An FSA is useful in and only if it is start-useful and every state has at least one reachable final state. See Figure~\ref{Fig:lang-2}.\\
  
\begin{figure}[hbtp]
\begin{center}
   \includegraphics[width=7cm,height=4cm]{fsa-lang-2.eps}
\caption{An example useful FSA.}
\label{Fig:lang-2}
\end{center}
\end{figure}

\noindent
A state may have more than one transition with the same label. In this case  the target state is chosen arbitrary at random.\\

\noindent
We can add a special symbol $\epsilon$ in the alphabet. If $\epsilon$ is among the labels of the arc going out from the state the transition occurs to the state the arc with label $\epsilon$ leads without reading the input. See Figure~\ref{Fig:lang-3}.
\begin{figure}[hbtp]
\begin{center}
   \includegraphics[width=8cm,height=5cm]{fsa-lang-33.eps}
\caption{An example of more general FSA.}
\label{Fig:lang-3}
\end{center}
\end{figure}


\color{blue}\begin{exercise}
Try to show the language accepted by the FSA shown in Figure~\ref{Fig:lang-2} and Figure~\ref{Fig:lang-3}.
\end{exercise}\color{black}



\clearpage
\section{Formal Language Theory}
The concept of the finite state machine comes from linguistics, or to be more specific, Formal Language Theory.\\

\noindent
In formal language theory, a language is a set of strings. A string is a sequence of symbols chosen from preset set of specific symbols called the vocabulary. All legal symbols are made up of letter from alphabet.\\

\noindent
A rule that generate a string is called {\it grammar} and those strings are called {\it language}. A machine such as Finite state automaton can recognize whether the language is legitimate or not.


\noindent
Let's make a toy example of formal language.
\begin{itemize}
\setlength{\itemsep}{0pt}
\item {\it Strings over \{a,b,c\} starting with a.}
   \begin{itemize}
   \item Example is $\{a, ab, ac, abc, abccc, acbbbbbbc, ...\}$ and $\{bc, cab\}$ is not example.
   \end{itemize}
\item {\it Strings over \{a,b,c,d\} in alphabetical order.}
   \begin{itemize}
   \item Example is $\{acd, bcd, c, abcd, ...\}$ and $\{ba, dca, ddabc\}$ is not example.
   \end{itemize}
\item {\it Strings that construct a palindrome over all the Roman alphabet with punctuation, capitalization, and spacing being ignored.} 
   \begin{itemize}
   \item Examples are "Never odd or even." "Madam, I'm Adam." or Madam in Eden, I'm Adam." and "I am a cat." is not.
   \end{itemize}
\end{itemize}

\subsection{Grammar to generate language vs. Machine to recognize language}
Let's now compare a grammar to generate regular language and FSA to recognize it. See Figure~\cite{Fig:grammar-vs-machine}.

\begin{figure}[hbtp]
\begin{center}
   \includegraphics[width=8cm,height=5cm]{fsa-vs-grammar.eps}
\caption{A tiny example of grammar to generate regular language and FSA to recognize it.}
\label{Fig:grammar-vs-machine}
\end{center}
\end{figure}




Again take 
\begin{quote}
string over $\{a, b, c\}$ with alphabetical order.
\end{quote}
as an example.\\


\noindent
This language can be generated by a grammar and recognized by the FSA shown in Figure\cite{Fig:lang-3}.

\begin{table}[h]
\begin{center}
\begin{tabular}{l l l} \hline \hline
$S$   & $\Rightarrow$  & $aS_1$ \\
$S$   & $\Rightarrow$  & $bS_2$ \\
$S$   & $\Rightarrow$  & $c$    \\
$S_1$ & $\Rightarrow$  & $bS_2$ \\
$S_1$ & $\Rightarrow$  & $c$    \\
$S_2$ & $\Rightarrow$  & $c$    \\ \hline \hline
\end{tabular}
\end{center}
\end{table}

\begin{figure}[h]
\begin{center}
   \includegraphics[width=8cm,height=5cm]{fsa-regular.eps}
\caption{A FSA that can recognize a string over $\{a,b,c\}$ in alphabetical order.}
\label{Fig:lang-3}
\end{center}
\end{figure}

\noindent
For example, we can generate $abc$ and $bc$ from $S$ as follows:
\begin{displaymath}
S \Rightarrow  aS_1  \Rightarrow a(bS_2) = abS_2 \Rightarrow \Rightarrow abc
\end{displaymath}

\begin{displaymath}
S \Rightarrow  bS_2  \Rightarrow bc
\end{displaymath}

\noindent
Here we call $a$, $b$, $c$ terminal, and $S$, $S_1$, $S_2$  non-terminal.\\

\noindent
Then can sequences of a's followed by an equal number of b's $a^nb^n$,
or 
palindrome over $\{a, b\}$ generate in this way? The answer is no. it's not possible.\\

\noindent
But, instead palindrome over \{a,b\} is simply generated by the grammar

\begin{table}[h]
\begin{center}
\begin{tabular}{l l l} \hline \hline
$S$   & $\Rightarrow$ $ab$     \\
$S$   & $\Rightarrow$ $aSb$    \\ \hline \hline
\end{tabular}
\end{center}
\end{table}
\noindent
But this is no more Finite State Grammar in which the rule should be of the form
\begin{table}[h]
\begin{center}
\begin{tabular}{l l l} \hline \hline
$S$   & $\Rightarrow$ & $aT$    \\ \hline \hline
\end{tabular}
\end{center}
\end{table}

\subsection{Generative Grammar}
Generative grammar is a grammar to define a set of languages somehow resembles a natural language.

\subsubsection{Finite-state grammar}
Let's take the above mentioned grammar as an example, that is, the grammar that generates:
\begin{itemize}
\setlength{\itemsep}{0pt}
\item[$\cdot$] {\it Strings over \{a,b,c\} in alphabetical order.}
\end{itemize}

\color{blue}
\begin{exercise}
Design an FSM which tests strings of the grammar is legal or not.
\end{exercise}
\color{black}

\noindent
We now take a different aspects. We are not testing if a string is accepted or rejected, but {\it how we generate a string that will be accepted as legitimate string of the grammar?"}


\noindent
Let's $S$ be the start symbol. ... \\

\noindent
Where $S$, $S_1$, $S_2$, and $S_3$, are called non-terminal and a, b, and c are called terminal.\\

\noindent
This grammar corresponds to an FSA that recognizes all and only the sentences it generates. Thus,\\

\color{red}
\begin{formula}[Finite State Grammar] \label{rule-1}
Any grammar that is made up of only rules of the form $A \rightarrow bC$ where A, B are non-terminals and b is a terminal has a corresponding FSA. This is called Finite State Grammars.
\end{formula}
\color{black}


\noindent
Let's summarize here. Assuming we have one grammar, we can design two distinct algorithms. One is to generate strings that follow the grammar, and the other is to see if a string follows the grammar. So what we have studied so far is Finite state grammar is an example of the former and finite state automaton is an example of the latter. \\


\color{blue}\begin{table}[h]
\begin{center}
\begin{tabular}{c c} \hline \hline
Grammar               & Machine to test           \\ \hline
Finite State Grammar  & Finite State Automaton    \\ \hline\hline
\end{tabular}
\end{center}
\end{table}\color{black}


\color{blue}
\begin{exercise}
Can we design a grammar which creates palindrome?
\end{exercise}
\color{black}

\noindent
The answer is no. We need an another grammar.

\subsubsection{Yet another way of represent FSA}
For the next three subsections, we see yet another way of represent a schematic diagram of Finite State Automaton. See Figure~\cite{Fig:t-fsa}
\begin{figure}[h]
\begin{center}
   \includegraphics[width=8cm,height=5cm]{t-fsa.eps}
\caption{A FSA that can recognize a string over $\{a,b,c\}$ in alphabetical order.}
\label{Fig:t-fsa}
\end{center}
\end{figure}


\subsubsection{Context-free Grammar \& Pushdown Automaton}
\noindent
{\bf $\bullet$ Context-free Grammar}\\

\noindent
We now look at a more flexible rule:

\begin{table}[h]
\begin{center}
\begin{tabular}{l l l} \hline \hline
$S$   & $\Rightarrow$  & $\alpha$    \\ \hline \hline
\end{tabular}
\end{center}
\end{table}
\noindent
where $\alpha$ is a non-empty sequence either terminal or non-terminal, such as $ab$ or $aSb$.\\

\noindent
{\bf $\bullet$ Pushdown Automaton}\\
A PDA is defined by (i) State to start, (ii) alphabet (iii) coins for push or pop on stack. If stack is empty when all inputs are read then the series of inputs will be accepted. Otherwise, like not possible to proceed or still stack is not empty when input was finished, the input was rejected. \\

\noindent
We can design PDA in a similar way when we design FSA by a transition table. To generate $a^nb^n$ over $\{a,b\}$, for example, the transition table is as follows:

\begin{table}[h]
\begin{center}
\begin{tabular}{c c c c} \hline \hline
current state  & input  &  action & next state \\ \hline
A              & a      &  push     & A        \\
\hspace{.1in}  & b      &  push     & A        \\
B              & a      &  pop      & A        \\
\hspace{.1in}  & b      &  pop      & A        \\ \hline \hline
\end{tabular}
\end{center}
\end{table}

\noindent
Or to generate palindrome over $\{a,b\}$:
\begin{table}[h]
\begin{center}
\begin{tabular}{c c c c} \hline \hline
current state  & input  &  action & next state \\ \hline
A              & a      &  push red     & A        \\
\hspace{.1in}  & b      &  push blue    & A        \\
\hspace{.1in}  & \#     &  nothing      & B        \\
B              & a      &  pop  red     & B        \\
\hspace{.1in}  & b      &  pop  blue    & B        \\ \hline \hline
\end{tabular}
\end{center}
\end{table}

\noindent
Notice that "\#" is a symbol to let the machine know this is the center, such as $aabbb\#bbbaa$.\\

\noindent
See a schematic diagram of pushdown automaton below.
\begin{figure}
\begin{center}
   \includegraphics[width=8cm,height=5cm]{t-pushdown.eps}
\caption{A schematic diagram of pushdown automaton.}
\label{Fig:lang-3}
\end{center}
\end{figure}

\noindent
As PDA may use a set of coins with different colors to push or pop in the stack.\\

\noindent
{\bf $\bullet$ $a^nb^n$ type of sentence in English}\\
\noindent
The above examples are not a meaningless toy example. Actually in English we come across a same kind of structure. See

\begin{quote}
{\it The dog the cat chased died.}
\end{quote}
This is modified from
\begin{quote}
{\it The dog died.}
\end{quote}
Similarly:
\begin{quote}
{\it The dog that the cat chased died.}
\end{quote}
Or
\begin{quote}
{\it The dog the cat the mouse bite chased died.}
\end{quote}
Further
\begin{quote}
{\it The dog the cat the mouse the monkey loved bite chase died.}
\end{quote}
All of these above sentences are grammatically correct.\\

\noindent
Yet the other example in English is
\begin{quote}
{\it Anyone who feels that if so-many more students whom we haven’t actually admitted are sitting in on the course than ones we have that the room had to be changed, then probably auditors will have to be excluded, is likely to agree that the curriculum needs revision.}
\end{quote}

\noindent
The main sentence is:
\begin{quote}
Anyone is likely to agree that the curriculum needs revision.
\end{quote}
But many clauses (sub-sentences) or phrases are nested in it.  That is,
\begin{itemize}
\setlength{\itemsep}{0pt}
\item[$\cdot$] We haven't actually admitted.
\item[$\cdot$] Student are sitting in.
\item[$\cdot$] So many more students are sitting that the room had to be changed. 
\item[$\cdot$] more students than ones we have
\end{itemize}
\noindent
Namely, the structure is:
\begin{quote}
Anyone who feels that if so many more ... whom he ... than ... that ... then ... must ...
\end{quote}

\noindent
The same holds in a sentence including "either ... or ..."


\subsubsection{Context-sensitive Grammar \& Linear-bounded Automaton}
\begin{table}[h]
\begin{center}
\begin{tabular}{l l l} \hline \hline
$\alpha A \beta$   & $\Rightarrow$  &  $\alpha \gamma \beta$    \\ \hline \hline
\end{tabular}
\end{center}
\end{table}
\noindent
where $A$ is a single non-terminal, $\alpha$ and $\beta$ are strings of non-terminals and terminals, and $\gamma$ is a non-empty string of non-terminals and terminals.\\

\noindent
{\bf $\bullet$ Example 1: $a^n b^n c^n$}\\
\begin{table}[h]
\begin{center}
\begin{tabular}{l l l} \hline \hline
$S$        & $\Rightarrow$  & $a S S_1 S_2 S_3$ \\
$S$        & $\Rightarrow$  & $a S_1 S_2 S_3$   \\
$S_2 S_1$  & $\Rightarrow$  & $S_4 S_1$         \\
$S_4 S_1$  & $\Rightarrow$  & $S_4 S_2$         \\
$S_4 S_2$  & $\Rightarrow$  & $S_1 S_2$         \\
$a   S_1$  & $\Rightarrow$  & $a   b  $         \\
$b   S_1$  & $\Rightarrow$  & $b   b  $         \\
$b   S_2$  & $\Rightarrow$  & $b   c  $         \\
$c   S_2$  & $\Rightarrow$  & $c   c  $         \\  \hline \hline
\end{tabular}
\end{center}
\end{table}
\noindent
The generation of {\it "aaabbbccc"} is:
\begin{quote}
$S$ $\Rightarrow$ $a S S_1 S_2$ $\Rightarrow$ $a a S H_1 H_2 H_1 H_2$ $\Rightarrow$ $\cdots$ $\Rightarrow$ $aaabbbccc$
\end{quote}

\noindent
{\bf $\bullet$ Example 2: $\{ xx | x \in {a, b}^{*}\}$\\
\begin{table}[h]
\begin{center}
\begin{tabular}{l l l} \hline \hline
$S$        & $\Rightarrow$  & $a S_1 S$         \\
$S$        & $\Rightarrow$  & $b S_2 S   $         \\
$S$        & $\Rightarrow$  & $S_3       $         \\
$S_1 a$    & $\Rightarrow$  & $a S_1     $         \\
$S_2 a$    & $\Rightarrow$  & $a S_2     $         \\
$S_1 a$    & $\Rightarrow$  & $a S_1     $         \\
$S_2 b$    & $\Rightarrow$  & $b S_2     $         \\
$S_1 S_3$  & $\Rightarrow$  & $S_1 a     $         \\
$S_2 S_3$  & $\Rightarrow$  & $S_3 b     $         \\
$S_3$      & $\Rightarrow$  & $\epsilon  $         \\  \hline \hline
\end{tabular}
\end{center}
\end{table}
\begin{figure}
\begin{center}
   \includegraphics[width=12cm,height=7.5cm]{t-linear-bounded.eps}
\caption{A schematic diagram of Linear-bounded Automaton.}
\label{Fig:lang-3}
\end{center}
\end{figure}

\subsection{Un-restricted Natural language \& Turing Machine}

\begin{figure}
\begin{center}
   \includegraphics[width=14cm,height=7cm]{t-turing-m.eps}
\caption{A schematic diagram of Turing machine.}
\label{Fig:lang-3}
\end{center}
\end{figure}



%% -----
\subsubsection{Natural Language Grammar \& Turing machine}

\noindent
{\bf $\bullet$ Any Grammar}\\

\noindent
{\bf $\bullet$ Turing Machine}\\


\subsection{Summary of Grammar and machine to test}
\color{blue}
\begin{table}[h]
\begin{center}
\begin{tabular}{l c l} \hline \hline
Grammar                    & Rule                                 & Machine to test          \\ \hline
Finite State Grammar       & $A \Rightarrow aB$                   & Finite State Automaton   \\ 
Context-free Grammar       & $A \Rightarrow \alpha$               & Pushdown Automaton       \\ 
Context-sensitive Grammar  & $\beta A \gamma \Rightarrow \alpha $ & Linear-bounded Automaton \\ 
Unrestricted Grammar       & {\it no restricted}                  & Turing Machine           \\ \hline \hline
\end{tabular}
\end{center}
\end{table}\color{black}



\section{Stochastic FSA}
(Let me skip this sub-topic.)

\clearpage
\section{Hidden Markov Model}
This subsection describes what is Hidden Markov Model\footnote{Named after a mathematician Andrei Andreyevich Markov who were born in Ryazan, Russia in 1856 and died in Petrograd, Russia in 1922.}, taking 3 examples from the wonderful tutorial on Hidden Markov Model by Ravinar\footnote{L.~R.~Ravinar (1989) "a tutorial on Hidden Markov Models and selected applications in speech recognition." Proceedings of the IEEE Vol. 77 No. 22.}. Nowadays almost all speech recognition systems use this model. Or many areas in computational molecular biology such as grouping amino-acid sequences into protein families, or fault detection.\\

\subsection{Markov Process}
Before we study Hidden Markov Model, let's see Markov process in general. Image a system with $N$ states, each of which can transfers to another state, or to itself, with a probability. To be more specific, state $i$ transfer to the state $j$ with a probability $a_{ij}$.


\begin{displaymath}
a_{ij}=p(q_{t}=S_i|q_{t-1}=S_j)
\end{displaymath}
This is called $N$-state Markov Model. For example, assume now $N=3$, we have nine such transition probability and we can represent them as the matrix $A$.
\begin{eqnarray}
\nonumber
A =
\left(
\begin{array}{ccc}
a_{11} & a_{12} & a_{13}      \\
a_{21} & a_{22} & a_{23}      \\
a_{31} & a_{32} & a_{33}
\end{array}
\right).
\end{eqnarray}

\subsubsection{A 3-state Markov model of the weather -- Not yet "hidden" though}
We now take a daily weather transition as an example. Imagine the weather at noon everyday. One day it's rain, the next day it's cloudy, the third day it's cloudy again, the fourth day it's fine, the fifth day it's rain again, the sixth day it's fine, and so on. \\

\noindent
Let's assume the transition probability is:


\begin{eqnarray}
\nonumber
A =
\left(
\begin{array}{l|cccc}
\hspace{.01in} & Fine & Cloudy & Rain \\ \hline
Fine           & 0.7 & 0.1 & 0.2      \\
Cloudy         & 0.5 & 0.4 & 0.1      \\
Rain           & 0.6 & 0.3 & 0.1      \\
\end{array}
\right).
\end{eqnarray}

\noindent
Or, schematically,

\begin{figure}[h]
\begin{center}
\includegraphics[width=6cm,height=4.5cm]{weather.eps}
\end{center}
\caption{A toy example of State transitions between three distinct weathers.}
\end{figure}


\color{blue}\begin{exercise}
Calculate the probability of the observation during a 7 day in a row.
\begin{displaymath}
sunny-sunny-sunny-rainy-rainy-sunny-cloudy-sunny
\end{displaymath}
%% under the Malkov Model above.
\end{exercise}\color{black}



\subsection{Hidden Markov Model}
Then what is Hidden Markov Model? Assume now we have $N$ states. The probability of the first state to be started with is $i$-th state is denoted.\\
\begin{displaymath}
 \pi_i,  \hspace{.2in} i = 1,2,\cdots, N.
\end{displaymath}
\noindent
Then the probability of transition from state $i$ to state $j$ is $a_{ij}$. Let's denote this with the matrix $A$:
\begin{displaymath}
A = \{ a_{ij} \},    \hspace{.2in} i = 1,2,\cdots, N.
\end{displaymath}

\noindent
We further assume each state results in one of $M$ distinct observations:
\begin{displaymath}
o_1, o_2, o_3, \cdots, o_M.
\end{displaymath}

\noindent
The probability that state $S_i$ results in the observation $o_j$ is denoted as $b_{ij}$ also denoted with the matrix $B$:
\begin{displaymath}
B = \{ b_{ij} \},    \hspace{.2in} i = 1,2,\cdots, M.
\end{displaymath}

\noindent
The important thing is, all we can know is only a series of observations. we cannot know the state that each of those observations has been resulted from. The state transition is hidden to us. This is the reason of the we call it Hidden Markov Model. \\

%% Let's assume we have $N$ distinct states each of which results in $M$ distinct observations. 
%% What we need now is the state transition probability $p(S_t|S_{t-1}$ and the the probability of output from each of the state 
\noindent
Let's take an example when $N=2$ and $M=4$.

\begin{eqnarray}
\nonumber
B =
\left(
\begin{array}{cccc}
b_{11} & b_{12} & b_{13} & b_{14}     \\
b_{21} & b_{22} & b_{23} & b_{24} 
\end{array}
\right).
\end{eqnarray}


\begin{figure}[h]
\begin{center}
\includegraphics[width=9cm,height=5cm]{state-observation-2.eps}
\end{center}
\caption{A schematic diagram of Hidden Markov model with 2 states and 4 observations.}
\end{figure}

\noindent
Now assume a series of observations was: 
\begin{displaymath}
O=\{o_1, o_2, o_3, \cdots, o_T\}
\end{displaymath}

\noindent
Let us now denote the state at time $t$ as $q_t$. Generally speaking, the transition probability depends on all those states it has shifted from the start. That is,
\begin{displaymath}
a_{ij}=p(S_j).
\end{displaymath}
Then let's think of just a special case where the state at time $t$ is only affected by the state at time $t-1$. Then  
\noindent
Notation \\
\begin{displaymath}
\lambda = \{\pi, A, B\}
\end{displaymath}
\noindent

\noindent
We express the state at time $t$ as $q_t$, that is, $q_t = S_i$ is the state at time $t$ is $S_i$. 
$o_t$ is observation at time $t$.\\

\noindent
Then the probability of this observation given the model $\lambda$ is 
\begin{displaymath}
p(O|\lambda) = \sum_q \pi_{q_0} \prod_{t=1}^{T} {a_{q_{t-1}}a_{q_t} b_{q_t}o_t}
\end{displaymath}


\subsubsection{An example: Fair dice and biased dice} 
Now let's see an example. Assume we have two dices. One is fair dice and the other is biased one. We have two states. The first state is the fair dice, and the second state is the biased one. Each gives one of 6 observations with a probability distribution. For example, fair coin (state 1), of course, results in either of 1, 2, 3, 4, 5, or 6 with the equal probability, namely 1/6, while the biased coin (state 2) results in 1, 2, 3, 4, and 5 with the probability of 1/10 and 1/2 for 6. Assume transition probability between two states is 
\begin{eqnarray}
\nonumber
A =
\left(
\begin{array}{cc}
0.90 & 0.05     \\ 
0.10 & 0.95
\end{array}
\right).
\end{eqnarray}

\noindent
See the Figure below. \\

\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm,height=4cm]{dice.eps}
\end{center}
\caption{A toy example of a fair dice and biased one.}
\label{Fig:dice}
\end{figure}

\noindent
Assume we cannot know which dice is used. Behind the curtain a hidden man changes the dice from time to time according to the probability distribution $A$, with the first dice is chosen according to the probability $\pi$. All we can observe is the result of the dice, such as:\\

\noindent
Then, a question is, e.g., "How likely the following result will occur?" 

\begin{figure}[h]
\begin{center}
	\includegraphics[width=7cm,height=0.5cm]{result-dice-1.eps}
\hspace{.1in}\\Or\\\hspace{.1in}\\
	\includegraphics[width=7cm,height=0.5cm]{result-dice-2.eps}
\end{center}
\end{figure}


\noindent
Or, we can imagine the situation at a casino, where a roulette dealer tries to switch his roulette machine a fair mode and a biased mode.


\subsubsection{Another example: Coin toss models}
Now behind the curtain a dealer tosses coins several times. And each time the dealer tells us the result is {\it "Head"} or {\it "Tail."}\\

\noindent
The dealer has a multiple coins each has a different probability to result in Head or Bottom. The dealer changes from one coin to another using a prefixed transition probability table. Then assume the result was
\begin{quote}
{\it Head, Head, Head, Tail, Head, Tail, Head, Head, Head, Tail, Tail, Head}
\end{quote}
We might guess that the occurrences of {\it Head} are too many for the coins are fair. Then the question is, "what happens behind the curtain?" \\
 
%% \begin{figure}[h]
%% \begin{center}
%% \includegraphics[width=5cm,height=3cm]{coin-1.eps}
%% \end{center}
%% \caption{A coin model assuming one coin.}
%% \end{figure}

\noindent
{\bf Two coin model}\\
\noindent
We suppose the dealer has two unfair coins and the dealer follows the transition rule

\begin{eqnarray}
\nonumber
A =
\left(
\begin{array}{l|cc}
\hspace{.01in} & Coin-1      & Coin-2       \\ \hline
Coin-1         & a_{11}    & a_{12}     \\
Coin-2         & a_{21}    & a_{22}     \\
\end{array}
\right).
\end{eqnarray}

\noindent
And each coin result in {\it Head} or {\it Tail} is from the probability table:
 
\begin{eqnarray}
\nonumber
A =
\left(
\begin{array}{l|cc}
\hspace{.01in} & Coin-1 & Coin-2            \\ \hline
Head           & b_{11}    & b_{12}     \\
Tail           & b_{21}    & b_{22}     \\
\end{array}
\right).
\end{eqnarray}

\noindent
Further, the dealer start the tossing with $i$-th coin ($i=1,2$) with the probability $\pi_i$. See the Figure below.

\begin{figure}[h]
\begin{center}
\includegraphics[width=12cm,height=4cm]{coin-2.eps}
\end{center}
\caption{A coin model assuming two coins.}
\end{figure}

\noindent
\color{blue}
Now our question might be to guess these 15 parameters, that is, $\lambda = \{\pi_i, A, B\}$ so that the observation is most likely, or equivalently, to maximize the probability of the observation:
\begin{displaymath}
p(Head, Head, Head, Tail, Head, Tail, Head, Head, Head, Tail, Tail, Head).
\end{displaymath}
\color{black}

\noindent
Or, the other question might be, \color{blue} "Which series of hidden states are most likely?" \color{black}\\


\noindent
{\bf Three coin model}\\
\noindent
Yet another possibility is, the dealer has 3 coins, not two. Then the state transition would be:

\begin{figure}[h]
\begin{center}
\includegraphics[width=13.5cm,height=6cm]{coin-3.eps}
\end{center}
\caption{A coin model assuming three coins.}
\end{figure}


\subsubsection{Further example: two urns with colored balls}
The final toy example is with two urns each contains a number of balls with red, blue, and purple color. The. The state-1 is the first urn and the state-2 is the second urn. Assume now, the first urn contains 5 red, 3 blue, and 1 purple balls while the second contains 2 red, 4 blue, and 2 purple balls. The dealer, behind the curtain, pick up one ball from either of the urns and tell us the color of the ball. Then the dealer return the ball to the urn he picked up the ball. This is repeated by changing urn to pick up the ball from according to the preset probability table as previous two examples. See the Figure.\\ 

\begin{figure}[h]
\begin{center}
	\includegraphics[width=9cm,height=4.5cm]{urn.eps}
\end{center}
\caption{A toy example of thought experiment with two urns each of which contains balls with three different colors.}
\end{figure}

\noindent
The question might be, \color{blue} "What is the probability of a series of observations?" \color{black}
 like in the Figure below.


\begin{figure}[h]
\begin{center}
	\includegraphics[width=6cm,height=0.2cm]{result-urn.eps}
\hspace{.1in}\\Or\\
	\includegraphics[width=6cm,height=0.2cm]{result-urn-2.eps}
\end{center}
\caption{A toy example of thought experiment with two urns each of which contains balls with three different colors.}
\end{figure}



\subsection{Three important problems}
As we have seen in examples above, three important questions raise.
\begin{itemize}
\setlength{\itemsep}{0pt}
\item Given $\lambda = \{\pi, A, B \}$, estimate "How likely the observation is?"  That is:
   \begin{itemize}
   \item[] $p(o_1, o_2, o_3, \cdots, o_T) = ?$
   \end{itemize}
\item Given $\lambda = \{\pi, A, B \}$, guess the most likely series of hidden states?
   \begin{itemize}
   \item[] $(q_1, q_2, q_3, \cdots, q_T)$
   \end{itemize}
so that we can predict the probability of the next state:
   \begin{itemize}
   \item[] $p(q_{T+1} | q_1, q_2, q_3, \cdots, q_T)$
   \end{itemize}
\item Given a series of observations $(o_1, o_2, o_3, \cdots, o_T)$ modify $\lambda$ so that it will maximize the $p(o_1, o_2, o_3, \cdots, o_T)$.
   \begin{itemize}
   \item[$\star$]This might be called {\it TRAINING}, or equivalently, {\it LEARNING} of the model.
   \end{itemize}
\end{itemize}


\noindent
To be more specific:
\begin{itemize}
\setlength{\itemsep}{0pt}
\item The Evaluation Problem
   \begin{itemize}
   \item[$\star$] Given the observation sequence $O$ and a model $lambda$, how do we efficiently evaluate the probability of being produced by the source model $/lambda$. That is, what is $p(O|\lambda)$.
   \end{itemize}
\item The Decoding Problem
   \begin{itemize}
   \item[$\star$] how to deduce from $O$ the most likely state sequence $q$ in a meaningful manner.
   \item[$\star$] it is important in many applications to have the knowledge of the most likely state sequence for several reasons. As an example, if we use the states of a word model to represent the distinct sounds in the word, it may be desirable to know the correspondence between the speech segments and the sounds of the word, because the duration of the individual speech segments provides useful information for speech recognition.
   \end{itemize}
\item The Estimation Problem
   \begin{itemize} 
   \item[$\star$] Given the observation $O$, how do we solve the inverse problem of estimating the parameters
in $\lambda$?
   \item[$\star$] Given an observation sequence (or a set of sequence) $O$, the estimation problem involves finding the "right" model parameter values that specify a model most likely to produce the given sequence. In speech recognition, this is often called "training,"
   \end{itemize}
\end{itemize}

\clearpage
\subsection{Stock Market Forecasting}
\subsubsection{A simple model - Not hidden}
Let's start with a very simple model in which states are not hidden. States are, for example, (1) good financial state also know as Bull State, (2) normal state, and (3) bad state a.k.a. Bear state. Assume state transition probabilities are know. When one state changes to another state, economy also change. For example, either of (i) large rise, (ii), small rise, (iii) no change, (iv) small fall, and (v) large fall. Then the phenomena will be shown as Figure \ref{Fig: no-hidden-economy}~\footnote{This example was taken from\\ Y. Zhang (2001) "Prediction of financial time series with Hidden Markov Models." Msc dissertation submitted to Simon Fraser University.}. 
\begin{figure}[h]
\begin{center}
\includegraphics[width=11cm,height=5cm]{stock-not-hidden.eps}
\end{center}
\caption{An example of three-state model for stock market forecasting.}
\label{Fig: no-hidden-economy}
\end{figure}

\noindent
Then we can calculate the probability of a series of state changes, like
\color{blue}
\begin{displaymath}
1 \rightarrow 1 \rightarrow 3 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 1
\end{displaymath}
\color{black}

\subsubsection{Hidden Markov Model for stock market forecasting}
States are financial states, as the example in the previous section. Or trends of investors, government's financial strategies, or something else. In any case each state reflects, or equivalently, results in, the stock price. Depending on what we want to forecast, the price is average of all stocks, or specific one stock, such as Microsoft Corporation, I.B.M, or Google Co, etc. Or instead of prices we can think of fluctuation of the price. Anyway those values are not discrete as we have studied so far, but a continuous value. We can digitize the value, but usually we analyse the continuous values. Therefore, the probability of one state to result in an observation should be also continuous. The most popular way is using a weighting sum of Gaussian probability distribution functions. This is called {\it Gaussian Mixture p.d.f.}
\begin{displaymath}
\sum_{i=1}^{k} N_i (\mu_i, \sigma_i)
\end{displaymath}
where
\begin{displaymath}
N(x, \mu, \sigma) = \frac{1}{n}\sum_{i=1}^{n}\frac{1}{h\sqrt{2\pi}}\exp(-\frac{1}{2}(\frac{x-x_i}{h})^2).
\end{displaymath}
For example:
\begin{figure}[h]
\begin{center}
\includegraphics[width=5cm,height=5cm]{gaussian-mixture-1.eps}
%%\includegraphics[width=5cm,height=5cm]{gaussian-mixture-3.eps}
\includegraphics[width=5cm,height=5cm]{gaussian-mixture-2.eps}
\end{center}
\caption{Two Gaussian-mixtures. Left $0.2*N(5, 1.2) + 0.5*N(2, 0.9) + 0.3* N(-2,  0.7)$ and right
$0.6*N(3, 0.6) + 0.1*N(0, 0.4) + 0.3* N(-2,  0.6)$} 
\end{figure}

\noindent
Or, if observation is not one dimensional value such as price, but a high-dimensional vector, like 
\begin{center}
{\it \{today's price, yesterday's price, price two day's ago \}}
\end{center}
then we use a high-dimensional Gaussian p.d.f.
\begin{equation} \label{eq: gaussian-multi-d} \nonumber
f(\mbox{\bf x}) = 
\frac{1}{(2\pi)^{d/2} \vert \Sigma_i \vert ^{1/2}}
\exp\{- \frac{1}{2}(\mbox{\bf x} - \boldsymbol{\mu}_i)^t {\Sigma_i}^{-1} (\mbox{\bf x} - \boldsymbol{\mu}_i)\}
\end{equation}
as we studied previously in Part I.\\

\noindent
Then imagine two-dice-example we saw in Figure~\ref{Fig:dice}. We have two states each of which result in observation of a continuous value following the Gaussian mixture p.d.f., instead of 1, 2, 3, 4, 5, or 6 following a probability like 1/6 or 1/10.\\

%% \subsection{A more general model}
\begin{figure}[h]
\begin{center}
\includegraphics[width=11cm,height=5cm]{continuous-hmm.eps}
\end{center}
\caption{A schematic diagram of two states each of which yields an observation with its Gaussian mixture p.d.f.}  
\end{figure}

\noindent
Recall a training of a HMM from a dataset $D$ is obtaining the model $M$ by maximizing
\begin{displaymath}
p(M|D)=\frac{p(D|M)p(M)}{p(D)}.
\end{displaymath}
\noindent
When, however, the model $M$ includes a set of continuous parameters $\theta$ the probability is
\begin{displaymath}
p(M|D)=\frac{\int p(D|\theta, M)p(\theta)d\theta p(M)}{p(D)}.
\end{displaymath}

\noindent
In stock market prediction, assume we have a series of observation $y_t$, that is 
\begin{displaymath}
D = \{y_1, y_2, y_3, \cdots, y_t\}.
\end{displaymath}
Then what we want to know is,
\begin{displaymath}
p(y_{t+1}|D) = \int p(y_{t+1}|\theta, M, D)p(\theta|M,D)p(M|D)d\theta dM.
\end{displaymath}
This is called {\it predictive distribution}.\\

\noindent
Now our hidden states are investment strategies or trend that are mixture of the weighted sum of 4 multi dimensional Gaussian pdf.
\begin{displaymath}
\sum_{i=1}^4 w_i N_i (\Sigma_i, \mu_i)
\end{displaymath}


\noindent
Then we can calculate how likely the series of state transitions which yields the series of change of prices we have observed, or more importantly, we can calculate the probability of the next state and most likely observations from the predicted state, that is, the price of tomorrow, for example. \\

\noindent
Probably most importantly, from a series of observations:
\begin{displaymath}
O_1, O_2, O_3, O_4, O_5, O_6, O_7, O_8, \cdots, O_T 
\end{displaymath}
you can optimize the parameters such that this series of observations is most likely, then
with those parameters you may infer the most likely series of hidden states,
\begin{displaymath}
S_1, S_2, S_3, S_4, S_5, S_6, S_7, S_8, \cdots, S_T
\end{displaymath}
and $S_{T+1}$ which means a most likely state of tomorrow. Finally, you can infer the most 
likely $O_{T+1}$ that will most likely result in from $S_{T+1}$. This is what we might want to know, namely, tomorrow's price. \\

\noindent
I wish your luck!



\clearpage
\section*{APPENDIX}
\subsection*{Genetic Algorithm}
\section{How we select parents?}
\noindent
Hopefully, {\it the better the fitness the more likely to be selected.}

\begin{itemize}
\item Three different versions of Selection.
   \begin{itemize}
   \item[$\star$] Truncation Selection (Simplest of the three):
      \begin{itemize}
      \item[$\cdot$] Select parents from the best some-percentage of the population.
      \end{itemize}
   \item[$\star$] Roulette Wheel Selection (or Fitness Proportionate Selection):
      \begin{itemize}
      \item[$\cdot$] Select such that the probability to be selected 
                     is proportional to the fitness value.
      \end{itemize}
      \item[]For example,
   \end{itemize}
\item[] To be more specific, sort the individual from low to high and 
calculate cumulative value of fitness as follows: 
\begin{table}[h]
\begin{center}
\begin{tabular}{c c} \hline
individual after sort & cumulative value of fitness \\
\hline
\#2                                     & 0.125 \\
\#3                                     & 0.250 \\
\#4                                     & 0.375 \\
\#5                                     & 0.625 \\
\#1                                     & 1.000 \\ \hline
\end{tabular} 
\end{center}
\end{table}
\item[]Then create a random number $r$ from 0 to 1 
if $r<0.125$ then select \#1, else if $r<0.250$ then select \#2
, else if $r<0.375$ then select \#3 and so on.
\end{itemize} 

\noindent
Note that even the worst fitness individual have a chance to be selected under
Roulette Selection however few it might be, while under Truncate Selection
worse individual have no chance to be selected. Tournament Selection could 
also select a worse individual except for the worst $q$ individuals. 
We can control the probability of selecting worse individual by changing $q$.


\begin{figure}[hbtp]
\begin{center}
   \includegraphics[width=8cm,height=4cm]{roulette-1.eps}
\end{center}
\end{figure}

\section{How parents produce a child?}
\subsection{Cross-over}
So-called {\it crossover} is exploited for the reproduce children.
Here, we see three different versions of crossover bellow.
      \begin{figure}[h]
      \begin{center}
      \includegraphics[width=12cm,height=9cm]{one-p-xover.eps}
      \end{center}
      \end{figure}

\subsection{Mutation}
We should give a mutation to introduce new genes. This is to avoid
for individuals in the population to be trapped into a {\it local minimum}.
The probability for mutation to occur is small --- typically 
{1/number-of-genes}. To be more specific,

\begin{quotation}
\noindent
{\it If a randomly generated number from 0.0 to 1.0 is smaller than the mutation rate then mutate otherwise do nothing.}
\end{quotation}

\end{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



