189 lines
7.7 KiB
TeX
Executable File
189 lines
7.7 KiB
TeX
Executable File
\documentclass[10pt,a4paper]{article}
|
|
\usepackage[utf8]{inputenc}
|
|
\usepackage[spanish]{babel}
|
|
\usepackage{amsmath}
|
|
\usepackage{amsfonts}
|
|
\usepackage{amssymb}
|
|
\usepackage{hyperref}
|
|
\usepackage{graphicx}
|
|
\usepackage{listings}
|
|
\usepackage{xcolor}
|
|
\usepackage{caption}
|
|
\usepackage{multicol}
|
|
\usepackage{pgf}
|
|
\usepackage{tikz}
|
|
\usetikzlibrary{automata,positioning,arrows}
|
|
|
|
\definecolor{codegreen}{rgb}{0,0.6,0}
|
|
\definecolor{codegray}{rgb}{0.5,0.5,0.5}
|
|
\definecolor{codepurple}{rgb}{0.58,0,0.82}
|
|
\definecolor{backcolour}{rgb}{0.95,0.95,0.92}
|
|
\definecolor{darkblue}{rgb}{0,0,.75}
|
|
|
|
\lstdefinestyle{mystyle}{
|
|
backgroundcolor=\color{backcolour},
|
|
commentstyle=\color{codegreen},
|
|
keywordstyle=\color{magenta},
|
|
numberstyle=\tiny\color{codegray},
|
|
stringstyle=\color{codepurple},
|
|
basicstyle=\ttfamily\footnotesize,
|
|
breakatwhitespace=false,
|
|
breaklines=true,
|
|
captionpos=b,
|
|
keepspaces=true,
|
|
numbers=left,
|
|
numbersep=5pt,
|
|
showspaces=false,
|
|
showstringspaces=false,
|
|
showtabs=false,
|
|
tabsize=2
|
|
}
|
|
|
|
\lstset{style=mystyle}
|
|
|
|
\lstloadlanguages{Matlab} %use listings with Matlab for Pseudocode
|
|
\lstnewenvironment{PseudoCode}[1][]
|
|
{\lstset{language=Matlab,basicstyle=\scriptsize, keywordstyle=\color{darkblue},numbers=left,xleftmargin=.04\textwidth,#1}}
|
|
{}
|
|
|
|
\renewcommand{\rmdefault}{ptm}
|
|
%\usepackage[all,cmtip]{xy}
|
|
%\usepackage{graphicx}
|
|
\author{Programación funcional para la física computacional}
|
|
\title{Patrones}
|
|
\begin{document}
|
|
\maketitle
|
|
|
|
\section*{Identificación de patrones}
|
|
|
|
La identificación de patrones es una de las funciones básicas de un lenguaje de programación. Al estudiar las computadoras como objeto teórico antes de llegar a los modelos computacionales, que ya vimos en una sección anterior, se estudian mecanismos más sencillos, regularmente llamados \emph{sub-Turing}, ya que no llegan a la potencia de de una máquina de Turing o el cálculo $\lambda$, pero pueden verse como casos específicos de esos modelos.
|
|
|
|
Estos niveles de modelos computacionales han sido estratificados por el lingüista Noam Chomsky. La jerarquía de Chomsky pone el siguiente orden:
|
|
|
|
\begin{enumerate}
|
|
\item Lenguajes regulares
|
|
\item Gramáticas independientes de contexto
|
|
\item Gramáticas sin restricciones
|
|
\end{enumerate}
|
|
|
|
El último nivel es el que puede identificarse completo con una máquina de Turing o el cálculo $\lambda$, los niveles inferiores pueden perfectamente simularse por una máquina de Turing, pero esos modelos no pueden simular toda máquina de Turing.
|
|
|
|
El primer nivel son las expresiones regulares, que están ligadas a la identificación de patrones. Las expresiones regulares son aceptadas por autómatas finitos deterministas, la forma más sencilla de mostrar que un lenguaje es regular es construyendo un autómata de este tipo. Un autómata finito determinista se define como:
|
|
|
|
\newtheorem{defi}{Definición}
|
|
\begin{defi}
|
|
Un autómata finito determinista es la quinteta
|
|
\begin{equation*}
|
|
M = (Q,\Sigma,\delta,s,F)
|
|
\end{equation*}
|
|
|
|
\begin{itemize}
|
|
\item $Q$ el conjunto finito de estados;
|
|
\item $\Sigma$ conjunto finito, alfabeto de entrada;
|
|
\item $\delta : Q\times \Sigma \rightarrow Q$ la función de transición;
|
|
\item $s\in Q$ es el estado inicial;
|
|
\item $F\subseteq Q$, los estados de aceptación o estados finales.
|
|
\end{itemize}
|
|
\end{defi}
|
|
|
|
Ya sea que se defina cada uno de los elementos o que se dibuje un diagrama como se muestra en la figura \ref{fig:auto}. Lo relevante es que pueden identificarse cadenas infinitas y de longitud infinita con sólo unos pocos estados y transiciones, misma que a su vez es la limitación para poder identificar cadenas en los lenguajes por arriba en la jerarquía de Chomsky. No hay más memoria que el estado en el que se encuentra.
|
|
|
|
\begin{figure}
|
|
\begin{center}
|
|
\begin{tikzpicture}
|
|
\node[state,initial,initial text= inicio] (S) {$S$};
|
|
\node[state,right=of S] (1) {$1$};
|
|
\node[state,right=of 1] (2) {$2$};
|
|
\node[state,right=of 2] (3) {$3$};
|
|
\node[state,accepting,right=of 3] (4) {$4$};
|
|
%\node[state,accepting, right=of 4] (4) {$5$};
|
|
|
|
|
|
\path [-stealth,thick]
|
|
(S) edge [left] node [yshift=0.3cm]{$a$} (1)
|
|
edge [loop above] node{$b$} ()
|
|
|
|
(1) edge [left] node [yshift=0.3cm]{$b$} (2)
|
|
edge [loop below] node{$a$} ()
|
|
(2) edge [bend right] node[yshift=0.3cm]{$b$} (S)
|
|
edge [right] node[yshift=0.3cm]{$a$} (3)
|
|
(3) edge [bend left] node[yshift=-0.3cm]{$a$} (1)
|
|
edge [right] node[yshift=-0.3cm]{$b$} (4)
|
|
(4) edge [loop above] node{$a,b$}();
|
|
|
|
|
|
\end{tikzpicture}
|
|
\end{center}
|
|
\caption{Automata finito determinista que acepta el lenguaje $\{ w\in\{ a,b \}^* \mid w \text{ contiene la subcadena } abab\}$.}
|
|
\label{fig:auto}
|
|
\end{figure}
|
|
|
|
|
|
Para identificar patrones en un lenguaje de programación debemos tomar en cuenta:
|
|
|
|
\begin{itemize}
|
|
\item Ser cuidadoso con mayúsculas y minúsculas, como carcateres son distintos y la identificación será distinta.
|
|
\item Usar escapes para caracteres especiales
|
|
\begin{itemize}
|
|
\item Caracteres de control ($\backslash t$, $\backslash n$, $\backslash r$.)
|
|
\item Caracteres numéricos (octal $\backslash nnn$, hexadecimal $\backslash xnn$, \textit{unicode} $\backslash unnnn$)
|
|
\item Caracteres especiales de escape ($\backslash ($)
|
|
\end{itemize}
|
|
\item Caracteres comodín: $.$, $\backslash w$, $\backslash s$,...
|
|
\item Anclas : \^, $\$ $, $*$
|
|
\end{itemize}
|
|
|
|
Para identificar patrones en \emph{haskell} necesitamos importar una librería, no está definido por \emph{default} en el lenguaje.
|
|
|
|
\begin{lstlisting}{language=Haskell}
|
|
import Text.Regex.Posix
|
|
let vocals = ``[aeiou]''
|
|
``Enunciado prueba'' =~ vocales :: Bool
|
|
``Enunciado prueba'' =~ vocales :: Int
|
|
``Enunciado prueba'' =~ vocales :: String
|
|
``Enunciado prueba'' =~ vocales :: (String,String,String)
|
|
\end{lstlisting}
|
|
|
|
Lo mismo se puede hacer con números, un ejemplo que puede parecer útil es hacer un programa que identifique un número de teléfono con un formato definido.
|
|
|
|
\begin{lstlisting}{language=Haskell}
|
|
let tel = "\\([0-9]{3}\\)[0-9]{3}\\-[0-9]{4}"
|
|
"Mi numero de telefono es: (555)643-1212"=~ tel :: String
|
|
\end{lstlisting}
|
|
|
|
Nota como se hace la identificación de patrones de acuerdo a lo mencionado líneas arriba.
|
|
|
|
De manera similar para identificar patrones en \emph{python}
|
|
|
|
\begin{lstlisting}{language=Python}
|
|
import re
|
|
vocales = "[aeiou]"
|
|
re.search(vocales, "Enunciado de ejemplo")
|
|
re.search(vocales,"Enunciado de ejemplo").group()
|
|
\end{lstlisting}
|
|
|
|
Las funcionalidades necesarias están en la librería \emph{re} (de \emph{regular expressions}), al igual que en \emph{haskell} se definen los patrones \emph{vocales}. Pero la diferencia está en que si simplemente se aplica el método \emph{re.search(vocales, ``Enunciado de ejemplo'')} lo que regresa es un objeto coincidente, en lugar del objeto que se busca. Para obtenerlo debe además escribirse otra línea idéntica pero finalizando con \emph{.group()}. Pero además de la búsqueda se puede trabajar con cincidencias
|
|
|
|
\begin{lstlisting}{language=Python}
|
|
import re
|
|
vocales = "[aeiou]"
|
|
re.match(vocales, "Enunciado de prueba")
|
|
re.match("E","Enunciado de ejemplo")
|
|
re.findall(vocales, "Enunciado de prueba")
|
|
\end{lstlisting}
|
|
|
|
Aún trabajando más con la identificación de patrones
|
|
|
|
\begin{lstlisting}{language=Python}
|
|
import re
|
|
sPrueba = "Esta es\tuna cadena de prueba.\nA fuerzas"
|
|
espacio = "[\s]"
|
|
re.split(espacio,sPrueba)
|
|
\end{lstlisting}
|
|
|
|
Lo que hace el programa es dividir la cadena en todas las subcadenas que se encuentran entre espacios, sea un espacio simple, un tabulador o un salto de línea.
|
|
|
|
|
|
|
|
\end{document}
|