\documentclass{article}
\usepackage{a4wide}
\usepackage{graphics}
\usepackage{graphicx}
\usepackage{color}
\usepackage{alltt}
\usepackage[dvips]{epsfig}
\usepackage{epic}
\usepackage{eepic}
\def\Ipe#1{\def\IPEfile{#1}\input{#1}}
\newenvironment{code}
{\begin{alltt}}
{\end{alltt}}
\title{\sf Finite Automata in Haskell: \\
An Exercise with the Language of Real Numbers}
\author{Jo\~ao Saraiva}
\date{\today}
\begin{document}
\maketitle
\section{Deterministic Finite Automaton}
\begin{figure}[htb!]
{\hrule\bigskip}
\begin{center}
\Ipe{FIGURES/Real.ipe}
\end{center}
\caption{Deterministic Finite Automaton for the Language of the
Real Numbers.}
{\bigskip\hrule}
\end{figure}
\begin{code}
module Language.HaLex.Examples.Real where
import Data.List
import Language.HaLex.RegExp
import Language.HaLex.Dfa
import Language.HaLex.Ndfa
import Language.HaLex.RegExp2Fa
import Language.HaLex.FaOperations
import Language.HaLex.FaAsDiGraph
import Language.HaLex.Minimize
import Language.HaLex.RegExpAsDiGraph
import Language.HaLex.Fa2RegExp
import qualified Language.HaLex.FaClasses as Fa
sinal'' = (Literal '-') `Or` (Literal '+') `Or` Epsilon
d = Literal 'd'
re_int = sinal'' `Then` d `Then` (Star d)
intdfa = (beautifyDfa . ndfa2dfa . regExp2Ndfa) re_int
d' = (Literal '0') `Or` (Literal '1') `Or` (Literal '2') `Or`
(Literal '3') `Or` (Literal '4') `Or` (Literal '5') `Or`
(Literal '6') `Or` (Literal '7') `Or` (Literal '8') `Or`
(Literal '9')
re_real = sinal'' `Then` (Star d')
`Then` ((Literal '.') `Or` Epsilon)
`Then` d' `Then` (Star d')
re_real' = sinal'' `Then` (Star d)
`Then` ((Literal '.') `Or` Epsilon)
`Then` d `Then` (Star d)
cre_real = "('+'|'-')?d*('.')?d+"
realdfa' = (beautifyDfa . ndfa2dfa . regExp2Ndfa) re_real
realdfa'' = (beautifyDfa . minimizeDfa . ndfa2dfa . regExp2Ndfa) re_real'
realdfa''' = (beautifyDfa . stdMinimizeDfa . ndfa2dfa . regExp2Ndfa) re_real'
realdfa'''' = beautifyDfa . minimizeNdfa . regExp2Ndfa $ re_real'
genGraph fa = tographvizIO fa "exp"
realdfa = Dfa ['+','-','.','0','1','2','3','4','5','6','7','8','9']
['A','B','C','D','E','F']
'A'
['C','E']
delta_realdfa
delta_realdfa :: Char -> Char -> Char
delta_realdfa 'A' '+' = 'B'
delta_realdfa 'A' '-' = 'B'
delta_realdfa 'A' '0' = 'C'
delta_realdfa 'A' '1' = 'C'
delta_realdfa 'A' '2' = 'C'
delta_realdfa 'A' '3' = 'C'
delta_realdfa 'A' '4' = 'C'
delta_realdfa 'A' '.' = 'D'
delta_realdfa 'B' '0' = 'C'
delta_realdfa 'B' '1' = 'C'
delta_realdfa 'B' '2' = 'C'
delta_realdfa 'B' '3' = 'C'
delta_realdfa 'B' '4' = 'C'
delta_realdfa 'B' '.' = 'D'
delta_realdfa 'C' '0' = 'C'
delta_realdfa 'C' '1' = 'C'
delta_realdfa 'C' '2' = 'C'
delta_realdfa 'C' '3' = 'C'
delta_realdfa 'C' '4' = 'C'
delta_realdfa 'C' '.' = 'D'
delta_realdfa 'D' '0' = 'E'
delta_realdfa 'D' '1' = 'E'
delta_realdfa 'D' '2' = 'E'
delta_realdfa 'D' '3' = 'E'
delta_realdfa 'D' '4' = 'E'
delta_realdfa 'E' '0' = 'E'
delta_realdfa 'E' '1' = 'E'
delta_realdfa 'E' '2' = 'E'
delta_realdfa 'E' '3' = 'E'
delta_realdfa 'E' '4' = 'E'
delta_realdfa _ _ = 'F'
isreal :: String -> Bool
isreal = Fa.accept realdfa
\end{code}
\section{Non-deterministic Finite Automaton}
\begin{figure}[htb!]
{\hrule\bigskip}
\begin{center}
\Ipe{FIGURES/RealNdfa.ipe}
\end{center}
\caption{Non-deterministic Finite Automaton for the Language of the
Real Numbers.}
{\bigskip\hrule}
\end{figure}
\begin{code}
realndfa = Ndfa ['+','-','.','0','1','2','3','4','5','6','7','8','9']
['A','B','C','D','E']
['A','C']
['C','E']
deltaNdfa
deltaNdfa 'A' (Just '+') = ['B']
deltaNdfa 'A' (Just '-') = ['B']
deltaNdfa 'A' Nothing = ['B']
deltaNdfa 'B' (Just '0') = ['C']
deltaNdfa 'B' (Just '1') = ['C']
deltaNdfa 'B' (Just '2') = ['C']
deltaNdfa 'B' (Just '3') = ['C']
deltaNdfa 'B' (Just '4') = ['C']
deltaNdfa 'B' (Just '5') = ['C']
deltaNdfa 'B' (Just '6') = ['C']
deltaNdfa 'B' (Just '7') = ['C']
deltaNdfa 'B' (Just '8') = ['C']
deltaNdfa 'B' (Just '9') = ['C']
deltaNdfa 'B' (Just '.') = ['D']
deltaNdfa 'C' (Just '.') = ['D']
deltaNdfa 'C' Nothing = ['B']
deltaNdfa 'D' (Just '0') = ['E']
deltaNdfa 'D' (Just '1') = ['E']
deltaNdfa 'D' (Just '2') = ['E']
deltaNdfa 'D' (Just '3') = ['E']
deltaNdfa 'D' (Just '4') = ['E']
deltaNdfa 'D' (Just '5') = ['E']
deltaNdfa 'D' (Just '6') = ['E']
deltaNdfa 'D' (Just '7') = ['E']
deltaNdfa 'D' (Just '8') = ['E']
deltaNdfa 'D' (Just '9') = ['E']
deltaNdfa 'E' (Just '0') = ['E']
deltaNdfa 'E' (Just '1') = ['E']
deltaNdfa 'E' (Just '2') = ['E']
deltaNdfa 'E' (Just '3') = ['E']
deltaNdfa 'E' (Just '4') = ['E']
deltaNdfa 'E' (Just '5') = ['E']
deltaNdfa 'E' (Just '6') = ['E']
deltaNdfa 'E' (Just '7') = ['E']
deltaNdfa 'E' (Just '8') = ['E']
deltaNdfa 'E' (Just '9') = ['E']
deltaNdfa _ _ = []
isrealNdfa = Fa.accept realndfa
\end{code}
Running hugs we have:
\begin{verbatim}
Real> isrealNdfa "-1.1"
True
Real> isrealNdfa "+12."
False
Real> isreal "-1.1"
True
Real> isreal "+12."
False
Real> isrealNdfa "122.122"
True
(1029 reductions, 1818 cells)
\end{verbatim}
\end{document}