Unidad 2 - Expresiones Regulares.

2.1. Definición formal de una ER.

Una expresión regular, a menudo llamada también regex, es una secuencia

de caracteres que forma un patrón de búsqueda, principalmente utilizada

para la búsqueda de patrones de cadenas de caracteres u operaciones de

sustituciones. Por ejemplo, el grupo formado por las cadenas Handel, Händel

y Haendel se describe con el patrón "H(a|ä|ae)ndel". La mayoría de las

formalizaciones proporcionan los siguientes constructores: una expresión

regular es una forma de representar a los lenguajes regulares (finitos o

infinitos) y se construye utilizando caracteres del alfabeto sobre el cual se

define el lenguaje.

Construcción de expresiones regulares

Específicamente, las expresiones regulares se construyen utilizando los

operadores unión, concatenación y clausura de Kleene. Además cada

expresión regular tiene un autómata finito asociado.

Alternación

Una barra vertical separa las alternativas. Por ejemplo, "marrón|castaño" se

corresponde con marrón o castaño.

Cuantificación

Un cuantificador tras un carácter especifica la frecuencia con la que éste

puede ocurrir. Los cuantificadores más comunes son +, ? y *:

+ El signo más indica que el carácter que le precede debe aparecer al menos

una vez. Por ejemplo, "ho+la" describe el conjunto infinito hola, hoola, hooola,

hoooola, etcétera.

? El signo de interrogación indica que el carácter que le precede puede

aparecer como mucho una vez. Por ejemplo, "ob?scuro" se corresponde con

oscuro y obscuro.

*El asterisco indica que el carácter que le precede puede aparecer cero, una,

o más veces. Por ejemplo, "0*42" se corresponde con 42, 042, 0042, 00042,

etcétera.

Agrupación

Los paréntesis pueden usarse para definir el ámbito y precedencia de los

demás operadores. Por ejemplo, "(p|m)adre" es lo mismo que "padre|madre",

y "(des)?amor" se corresponde con amor y con desamor.

Los constructores pueden combinarse libremente dentro de la misma

expresión, por lo que "H(ae?|ä)ndel" equivale a "H(a|ae|ä)ndel".

La sintaxis precisa de las expresiones regulares cambia según las

herramientas y aplicaciones consideradas, y se describe con más detalle a

continuación.

Su utilidad más obvia es la de describir un conjunto de cadenas, lo que resulta

de utilidad en editores de texto y aplicaciones para buscar y manipular textos.

Muchos lenguajes de programación admiten el uso de expresiones regulares

con este fin. Por ejemplo, Perl tiene un potente motor de expresiones

regulares directamente incluido en su sintaxis. Las herramientas

proporcionadas por las distribuciones de Unix (incluyendo el editor sed y el

filtro grep) fueron las primeras en popularizar el concepto de expresión

regular.

Expresiones regulares como lenguaje

Para especificar opciones dentro del texto a buscar se utiliza un lenguaje o

convención mediante el cual se le transmite al motor de búsqueda el resultado

que se desea obtener. Este lenguaje le da un significado especial a una serie

de caracteres. Por lo tanto cuando el motor de búsqueda de expresiones

regulares encuentre estos caracteres no los buscará en el texto en forma

literal, sino que buscará lo que los caracteres significan. A estos caracteres

se les llama algunas veces "meta-caracteres". A continuación se listan los

principales meta-caracteres y su función y cómo los interpreta el motor de

expresiones regulares.

Descripción de las expresiones regulares

El punto "." El punto se interpreta por el motor de búsqueda como "cualquier

carácter", es decir, busca cualquier carácter SIN incluir los saltos de línea.

Los motores de Expresiones regulares tienen una opción de configuración

que permite modificar este comportamiento. En .Net Framework se utiliza la

opción RegexOptions.Singleline para especificar la opción de que busque

todos los caracteres incluidos el salto de línea (\n).

El punto se utiliza de la siguiente forma: Si se le dice al motor de RegEx que

busque "g.t" en la cadena "el gato de piedra en la gótica puerta de getisboro

goot" el motor de búsqueda encontrará "gat", "gót" y por último "get". Nótese

que el motor de búsqueda no encuentra "goot"; esto es porque el punto

representa un solo carácter y únicamente uno. Si es necesario que el motor

encuentre también la expresión "goot", será necesario utilizar repeticiones,

las cuales se explican más adelante.

Aunque el punto es muy útil para encontrar caracteres que no conocemos, es

necesario recordar que corresponde a cualquier carácter y que muchas veces

esto no es lo que se requiere. Es muy diferente buscar cualquier carácter que

buscar cualquier carácter alfanumérico o cualquier dígito o cualquier no-dígito

o cualquier no-alfanumérico. Se debe tomar esto en cuenta antes de utilizar

el punto y obtener resultados no deseados.

La admiración "!" Se utiliza para realizar una "búsqueda anticipada

negativa". La construcción de la expresión regular es con el par de paréntesis,

el paréntesis de apertura seguida de un signo de interrogación y un signo de

exclamación. Dentro de la búsqueda tenemos la expresión regular. Por

ejemplo, para excluir exactamente una palabra, habrá que utilizar

"^(palabra.+|(?!Palabra).*)$"

La barra inversa o antibarra "\" Se utiliza para "marcar" el siguiente carácter

de la expresión de búsqueda de forma que este adquiera un significado

especial o deje de tenerlo. O sea, la barra inversa no se utiliza nunca por sí

sola, sino en combinación con otros caracteres. Al utilizarlo por ejemplo en

combinación con el punto "\." este deja de tener su significado normal y se

comporta como un carácter literal. De la misma forma, cuando se coloca la

barra inversa seguida de cualquiera de los caracteres especiales que

discutiremos a continuación, estos dejan de tener su significado especial y se

convierten en caracteres de búsqueda literal. Como ya se mencionó con

anterioridad, la barra inversa también puede darle significado especial a

caracteres que no lo tienen. A continuación hay una lista de algunas de estas

combinaciones:

\t — Representa un tabulador.

\r — Representa el "retorno de carro" o "regreso al inicio" o sea el lugar en

que la línea vuelve a iniciar.

\n — Representa la "nueva línea" el carácter por medio del cual una línea da

inicio. Es necesario recordar que en Windows es necesaria una combinación

de \r\n para comenzar una nueva línea, mientras que en Unix solamente se

usa \n y en Mac_OS clásico se usa solamente \r.

\a — Representa una "campana" o "beep" que se produce al imprimir este

carácter.

\e — Representa la tecla "Esc" o "Escape"

\f — Representa un salto de página

\v — Representa un tabulador vertical

\x — Se utiliza para representar caracteres ASCII o ANSI si conoce su código.

De esta forma, si se busca el símbolo de derechos de autor y la fuente en la

que se busca utiliza el conjunto de caracteres Latin-1 es posible encontrarlo

utilizando "\xA9".

\u — Se utiliza para representar caracteres Unicode si se conoce su código.

"\u00A2" representa el símbolo de centavos. No todos los motores de

Expresiones Regulares soportan Unicode. El .Net Framework lo hace, pero

el EditPad Pro no, por ejemplo.

\d — Representa un dígito del 0 al 9.

\w — Representa cualquier carácter alfanumérico.

\s — Representa un espacio en blanco.

\D — Representa cualquier carácter que no sea un dígito del 0 al 9.

\W — Representa cualquier carácter no alfanumérico.

\S — Representa cualquier carácter que no sea un espacio en blanco.

\A — Representa el inicio de la cadena. No un carácter sino una posición.

\Z — Representa el final de la cadena. No un carácter sino una posición.

\b — Marca la posición de una palabra limitada por espacios en blanco,

puntuación o el inicio/final de una cadena.

\B — Marca la posición entre dos caracteres alfanuméricos o dos no-

alfanuméricos.

Los corchetes "[ ]" La función de los corchetes en el lenguaje de las

expresiones regulares es representar "clases de caracteres", o sea, agrupar

caracteres en grupos o clases. Son útiles cuando es necesario buscar uno de

un grupo de caracteres. Dentro de los corchetes es posible utilizar el guion "-

" para especificar rangos de caracteres. Adicionalmente, los metacaracteres

pierden su significado y se convierten en literales cuando se encuentran

dentro de los corchetes. Por ejemplo, como vimos en la entrega anterior "\d"

nos es útil para buscar cualquier carácter que represente un dígito. Sin

embargo esta denominación no incluye el punto "." que divide la parte decimal

de un número. Para buscar cualquier carácter que representa un dígito o un

punto podemos utilizar la expresión regular "[\d.]". Como se hizo notar

anteriormente, dentro de los corchetes, el punto representa un carácter literal

y no un metacarácter, por lo que no es necesario antecederlo con la barra

inversa. El único carácter que es necesario anteceder con la barra inversa

dentro de los corchetes es la propia barra inversa. La expresión regular "[\dA-

Fa-f]" nos permite encontrar dígitos hexadecimales. Los corchetes nos

permiten también encontrar palabras aún si están escritas de forma errónea,

por ejemplo, la expresión regular "expresi[oó]n" permite encontrar en un texto

la palabra "expresión" aunque se haya escrito con o sin tilde. Es necesario

aclarar que sin importar cuantos caracteres se introduzcan dentro del grupo

por medio de los corchetes, el grupo sólo le dice al motor de búsqueda que

encuentre un solo carácter a la vez, es decir, que "expresi[oó]n" no encontrará

"expresioon" o "expresioón".

La barra "|"

Sirve para indicar una de varias opciones. Por ejemplo, la expresión regular

"a|e" encontrará cualquier "a" o "e" dentro del texto. La expresión regular

"este|oeste|norte|sur" permitirá encontrar cualquiera de los nombres de los

puntos cardinales. La barra se utiliza comúnmente en conjunto con otros

caracteres especiales.

El signo de dólar "$"

Representa el final de la cadena de caracteres o el final de la línea, si se

utiliza el modo multi-línea. No representa un carácter en especial sino una

posición. Si se utiliza la expresión regular "\.$" el motor encontrará todos los

lugares donde un punto finalice la línea, lo que es útil para avanzar entre

párrafos.

El acento circunflejo "^"

Este carácter tiene una doble funcionalidad, que difiere cuando se utiliza

individualmente y cuando se utiliza en conjunto con otros caracteres

especiales. En primer lugar su funcionalidad como carácter individual: el

carácter "^" representa el inicio de la cadena (de la misma forma que el signo

de dólar "$" representa el final de la cadena). Por tanto, si se utiliza la

expresión regular "^[a-z]" el motor encontrará todos los párrafos que den inicio

con una letra minúscula. Cuando se utiliza en conjunto con los corchetes de

la siguiente forma "[^\w ]" permite encontrar cualquier carácter que NO se

encuentre dentro del grupo indicado. La expresión indicada permite

encontrar, por ejemplo, cualquier carácter que no sea alfanumérico o un

espacio, es decir, busca todos los símbolos de puntuación y demás

caracteres especiales.

La utilización en conjunto de los caracteres especiales "^" y "$" permite

realizar validaciones en forma sencilla. Por ejemplo "^\d$" permite asegurar

que la cadena a verificar representa un único dígito "^\d\d/\d\d/\d\d\d\d$"

permite validar una fecha en formato corto, aunque no permite verificar si es

una fecha válida, ya que 99/99/9999 también sería válido en este formato; la

validación completa de una fecha también es posible mediante expresiones

regulares, como se ejemplifica más adelante.

Los paréntesis "()"

De forma similar que los corchetes, los paréntesis sirven para agrupar

caracteres, sin embargo existen varias diferencias fundamentales entre los

grupos establecidos por medio de corchetes y los grupos establecidos por

paréntesis:

Los caracteres especiales conservan su significado dentro de los paréntesis.

Los grupos establecidos con paréntesis establecen una "etiqueta" o "punto

de referencia" para el motor de búsqueda que puede ser utilizada

posteriormente como se denota más adelante.

Utilizados en conjunto con la barra "|" permite hacer búsquedas opcionales.

Por ejemplo la expresión regular "al (este|oeste|norte|sur) de" permite buscar

textos que den indicaciones por medio de puntos cardinales, mientras que la

expresión regular "este|oeste|norte|sur" encontraría "este" en la palabra

"esteban", no pudiendo cumplir con este propósito.

Utilizados en conjunto con otros caracteres especiales que se detallan

posteriormente, ofrece funcionalidad adicional.

El signo de interrogación "?"

El signo de interrogación tiene varias funciones dentro del lenguaje de las

expresiones regulares. La primera de ellas es especificar que una parte de la

búsqueda es opcional. Por ejemplo, la expresión regular "ob?scuridad"

permite encontrar tanto "oscuridad" como "obscuridad". En conjunto con los

paréntesis redondos permite especificar que un conjunto mayor de caracteres

es opcional; por ejemplo "Nov(\.|iembre|ember)?" permite encontrar tanto

"Nov" como "Nov.", "Noviembre" y "November". Como se mencionó

anteriormente, los paréntesis nos permiten establecer un "punto de

referencia" para el motor de búsqueda. Sin embargo, algunas veces, no se

desea utilizarlos con este propósito, como en el ejemplo anterior

"Nov(\.|iembre|ember)?". En este caso el establecimiento de este punto de

referencia (que se detalla más adelante) representa una inversión inútil de

recursos por parte del motor de búsqueda. Para evitarlo se puede utilizar el

signo de pregunta de la siguiente forma: "Nov(?:\.|iembre|ember)?". Aunque

el resultado obtenido será el mismo, el motor de búsqueda no realizará una

inversión inútil de recursos en este grupo, sino que lo ignorará. Cuando no

sea necesario reutilizar el grupo, es aconsejable utilizar este formato. De

forma similar, es posible utilizar el signo de pregunta con otro significado: Los

paréntesis definen grupos "anónimos", sin embargo el signo de pregunta en

conjunto con los paréntesis triangulares "<>" permite "nombrar" estos grupos

de la siguiente forma: "^(?<Día>\d\d)/(?<Mes>\d\d)/(?<Año>\d\d\d\d)$"; Con

lo cual se le especifica al motor de búsqueda que los primeros dos dígitos

encontrados llevarán la etiqueta "Día", los segundos la etiqueta "Mes" y los

últimos cuatro dígitos llevarán la etiqueta "Año".

Las llaves "{}"

Comúnmente las llaves son caracteres literales cuando se utilizan por

separado en una expresión regular. Para que adquieran su función de

metacaracteres es necesario que encierren uno o varios números separados

por coma y que estén colocados a la derecha de otra expresión regular de la

siguiente forma: "\d{2}" Esta expresión le dice al motor de búsqueda que

encuentre dos dígitos contiguos. Utilizando esta fórmula podríamos convertir

el ejemplo "^\d\d/\d\d/\d\d\d\d$" que servía para validar un formato de fecha

en "^\d{2}/\d{2}/\d{4}$" para una mayor claridad en la lectura de la expresión.

"\d{2,4}" Esta forma añade un segundo número separado por una coma, el

cuál indica al motor de búsqueda que como máximo debe aparecer 4 veces

la expresión regular \d. Los posibles valores son:

"^\d\d$" (mínimo 2 repeticiones)

"^\d\d\d$"(tiene 3 repeticiones, por lo tanto entra en el rango 2-4)

"^\d\d\d\d$" (máximo 4 repeticiones)

Nota: aunque esta forma de encontrar elementos repetidos es muy útil,

algunas veces no se conoce con claridad cuantas veces se repite lo que se

busca o su grado de repetición es variable. En estos casos los siguientes

metacaracteres son útiles.

El asterisco " * "

El asterisco sirve para encontrar algo que se encuentra repetido 0 o más

veces. Por ejemplo, utilizando la expresión "[a-zA-Z]\d*" será posible

encontrar tanto "H" como "H1", "H01", "H100" y "H1000", es decir, una letra

seguida de un número indefinido de dígitos. Es necesario tener cuidado con

el comportamiento del asterisco, ya que éste, por defecto, trata de encontrar

la mayor cantidad posible de caracteres que correspondan con el patrón que

se busca. De esta forma si se utiliza "\(.*\)" para encontrar cualquier cadena

que se encuentre entre paréntesis y se lo aplica sobre el texto "Ver (Fig. 1) y

(Fig. 2)" se esperaría que el motor de búsqueda encuentre los textos "(Fig.

1)" y "(Fig. 2)", sin embargo, debido a esta característica, en su lugar

encontrará el texto "(Fig. 1) y (Fig. 2)". Esto sucede porque el asterisco le dice

al motor de búsqueda que llene todos los espacios posibles entre los dos

paréntesis. Para obtener el resultado deseado se debe utilizar el asterisco en

conjunto con el signo de interrogación de la siguiente forma: "\(.*?\)" Esto es

equivalente a decirle al motor de búsqueda que "Encuentre un paréntesis de

apertura y luego encuentre cualquier secuencia de caracteres hasta que

encuentre un paréntesis de cierre".

El signo de suma "+"

Se utiliza para encontrar una cadena que se encuentre repetida una o más

veces. A diferencia del asterisco, la expresión "[a-zA-Z]\d+" encontrará "H1"

pero no encontrará "H". También es posible utilizar este metacarácter en

conjunto con el signo de interrogación para limitar hasta donde se efectúa la

repetición.

Grupos anónimos

Los grupos anónimos se establecen cada vez que se encierra una expresión

regular en paréntesis, por lo que la expresión "<([a-zA-Z]\w*?)>" define un

grupo anónimo que tendrá como resultado que el motor de búsqueda

almacenará una referencia al texto que corresponda a la expresión encerrada

entre los paréntesis.

La forma más inmediata de utilizar los grupos que se definen es dentro de la

misma expresión regular, lo cual se realiza utilizando la barra inversa "\"

seguida del número del grupo al que se desea hacer referencia de la siguiente

forma: "<([a-zA-Z]\w*?)>.*?</\1>" Esta expresión regular encontrará tanto la

cadena "<font>Esta</font>" como la cadena "<b>prueba</b>" en el texto

"<font>Esta</font> es una <b>prueba</b>" a pesar de que la expresión no

contiene los literales "font" y "B".

2.2. Operaciones

Unión o Alternativa: Consideremos dos lenguajes diferentes definidos sobre

el mismo alfabeto L1 ⊂ W(∑) y L2 ⊂ W(∑). Se denomina unión de ambos

lenguajes al lenguaje formado por las palabras de ambos lenguajes:

L1 U L2={ x | x ∈ L1 ó x ∈ L2}

Concatenación: Consideremos dos lenguajes definidos sobre el mismo

alfabeto, L1 y L2. La concatenación o producto de estos lenguajes es el

lenguaje L1 L2= { xy / x ∈ L1 y x ∈ L2} Las palabras de este lenguaje estarán

formadas al concatenar cada una palabra del primero de los lenguajes con

otra del segundo.

La concatenación de lenguajes con el lenguaje vació es ΦL = L Φ = Φ

Potencia de un lenguaje: Se define la potencia i-ésima de un lenguaje a la

operación de concatenarlo consigo mismo i veces.

Li= LLL ....L

|------------|

i

Clausura positiva de un lenguaje: Se define la clausura positiva de un

lenguaje L: ∞ L + = U L i i=1

Lenguaje obtenido uniendo el lenguaje con todas sus potencias posibles

excepto Lº. Si L no contiene la palabra vacía, la clausura positiva tampoco

Cierre o Clausura de un lenguaje: Se define el cierre o clausura de un

lenguaje L como:

∞

L* = U Li

i=0

Lenguaje obtenido uniendo el lenguaje con todas sus potencias posibles,

incluso Lº. Todas las clausuras contienen la palabra vacía.

Existen tres operaciones básicas que se pueden realizar sobre las ER:

Selección de alternativas: Se indica con el operador |(barra vertical). Si r y

s son ER, entonces r | s es una ER que define a cualquier cadena que

concuerde con una r o una s, también se dice que r | s , es la unión de los

lenguajes de r y s y lo podemos definir: L( r | s ) = L( r ) U L( s ). Esta operación

se puede extender a más de dos ER.

Concatenación: Se indica con la yuxtaposición de las ER. Si r y s son ER,

entonces rs es una ER que define a cualquier cadena que concuerde con la

concatenación de r y s , esta operación la podemos definir: L(rs) =

L(r)L(s).Esta operación se puede extender a más de dos ER.

Repetición o Cerradura: También se conoce con el nombre de cerradura de

Kleene. Se indica con el operador *. Si r es una ER, entonces r* es una ER

que define a las cadenas de caracteres representadas por la concatenación

repetida de r en n veces, o sea que lo podemos definir como: L(r*) = L(r)*o

también lo podemos definir como la unión infinita de conjuntos r :r* n = r 0 r 1

r 2...r n.

2.3 Aplicaciones en problemas reales.

Una de las principales aplicaciones de los hermanos Deitel, son

las expresiones regulares que facilitan la construcción de un compilador. A

menudo se utiliza una expresión regular larga y compleja para validar la

sintaxis de un programa. Si el código del programa no concuerda con la

expresión regular, el compilador sabe que hay un error de sintaxis dentro del

código.

Generalmente convierten la expresión regular a un autómata finito no

determinista y después construyen el autómata finito determinista.

Otra aplicación del mismo libro es en los editores de texto. También

encontramos a las expresiones regulares en la biología molecular. También

hay esfuerzos importantes para tratar de representar cadenas como

generadas por expresiones regulares o por lenguajes regulares.

El ejemplo más corriente es el de una dirección email. Imaginemos que

queremos filtrar las direcciones introducidas por los visitantes, para evitar

introducir en la base de datos la típica dirección basura ghghghghghghg.

Todos sabemos la estructura de una dirección email, formada por la cadena

nombreusuario, el signo @ y la cadena nombre dominio. También sabemos

que nombre dominio está formado por dos subcadenas, 'nombredomino', un

'.' y un sufijo 'com', 'net', 'es' o similar.

Por tanto la solución a nuestro problema es idear una expresión regular que

identifique una dirección email valida típica, y confrontarla con la cadena

(dirección email) pasada por el visitante

Por ejemplo:

<?

^[^@ ]+@[^@ ]+.[^@ .]+$

?>

Vamos a diseccionar nuestra expresión regular:

<?

^ // queremos decir que el primer carácter que buscamos

// debe estar al principio de la cadena a comparar.

[^@ ] // ese primer signo no debe ser ni el signo @

// ni un espacio

+ // y se repite una o mas veces

@ // luego buscamos el signo @

[^@ ]+ // Seguido de otro signo que no es un @ ni un

// espacio y se repite una o mas veces

. // Seguido de un .

[^@ .] // Seguido de un carácter que no sea ni @,

// ni espacio ni punto

+$ // Que se repite una o mas veces y el último esta

// al final de la cadena

?>

Y para comprobarlo en la práctica, usamos una de las funciones de php

relacionadas con las expresiones regulares:ereg().

Acudiendo al manual php, podemos averiguar que esta función tiene la

siguiente sintaxis:

ereg (string pattern, string string)

Busca en string las coincidencias con la expresión regular pattern. La

búsqueda diferencia entre mayúsculas y minúsculas.

Devuelve un valor verdadero si se encontró alguna coincidencia, o falso in no

se encontraron coincidencias u ocurrió algún error. Podríamos usar esta

funcion para un validador email con algo asi como:

<?

// establecemos una secuencia condicional: si la variable $op no existe y

// es igual a "ds", se muestra un formulario

if ($op != "ds") { ?>

<form>

<input type=hidden name="op" value="ds">

<strong>Tu email:</strong><br />

<input type=text name="email" value="" size="25" />

<input type=submit name="submit" value="Enviar" />

</form>

<?

}

// Si $op existe y es igual a "ds"m, se ejecuta la función ereg buscando

// nuestra cadena dentro del patrón $email que es la direccion enviada por

// el usuario desde el formulario anterior

else if ($op == "ds")

{

if (ereg("^[^@ ]+@[^@ ]+.[^@ .]+$", $email ) )

{

print "<BR>Esta dirección es correcta: $email"; }

else {echo "$email no es una dirección valida";}

}

?>

No hace falta advertir que se trata de un ejemplo muy elemental, que dará

por válida cualquier dirección email que tenga una mínima apariencia de

normalidad.

INSTITUTO TECNOLÓGICO DE LEÓN

INGENIERÍA EN SISTEMAS

COMPUTACIONALES

Trabajo de Investigación Unidad 4

PROFESOR:

ING. JOSE ARTURO AZCORRA VILLALOBOS

ALUMNO

Flores Guzmán Omar Jorge

LEÓN, GTO. 08 DE DICIEMBRE DEL 2014

Máquina de Turing

4.1 Definición formal de Maquina de Turing.

Una máquina de Turing es un dispositivo que manipula símbolos sobre una

tira de cinta de acuerdo a una tabla de reglas. A pesar de su simplicidad, una

máquina de Turing puede ser adaptada para simular la lógica de cualquier

algoritmo de computador y es particularmente útil en la explicación de las

funciones de una CPU dentro de un computador.

La máquina de Turing fue descrita por Alan Turing como una «máquina

automática» en 1936 en la revista Proceedings of the London Mathematical

Society,1 La máquina de Turing no está diseñada como una tecnología de

computación práctica, sino como un dispositivo hipotético que representa una

máquina de computación. Las máquinas de Turing ayudan a los científicos a

entender los límites del cálculo mecánico.

Turing dio una definición sucinta del experimento en su ensayo de 1948,

«Máquinas inteligentes». Refiriéndose a su publicación de 1936, Turing

escribió que la máquina de Turing, aquí llamada una máquina de computación

lógica, consistía en:

...una ilimitada capacidad de memoria obtenida en la forma de una cinta

infinita marcada con cuadrados, en cada uno de los cuales podría imprimirse

un símbolo. En cualquier momento hay un símbolo en la máquina; llamado el

símbolo leído. La máquina puede alterar el símbolo leído y su comportamiento

está en parte determinado por ese símbolo, pero los símbolos en otros

lugares de la cinta no afectan el comportamiento de la máquina. Sin embargo,

la cinta se puede mover hacia adelante y hacia atrás a través de la máquina,

siendo esto una de las operaciones elementales de la máquina. Por lo tanto

cualquier símbolo en la cinta puede tener finalmente una oportunidad.2

(Turing 1948, p. 61)

Una máquina de Turing que es capaz de simular cualquier otra máquina de

Turing es llamada una máquina universal de Turing (UTM, o simplemente una

máquina universal). Una definición más matemáticamente orientada, con una

similar naturaleza "universal", fue presentada por Alonzo Church, cuyo trabajo

sobre el cálculo lambda se entrelaza con el de Turing en una teoría formal de

la computación conocida como la tesis de Church-Turing. La tesis señala que

las máquinas de Turing capturan, de hecho, la noción informal de un método

eficaz en la lógica y las matemáticas y proporcionan una definición precisa de

un algoritmo o 'procedimiento mecánico'.

4.2 CONSTRUCCIÓN MODULAR DE UNA MÁQUINA DE TURING

Mediante esta Técnica se pueden desarrollar máquinas de Turing complejas

a partir de Bloques y a partir de máquinas más pequeñas mediante diagramas

de transiciones.

COMBINACIÓN DE MAQUINAS DE TURING

La construcción de máquinas de Turing se lleva a cabo mediante los

diagramas de transición y combinarlos de manera parecida a lo que se realiza

en la formación de la unión y concatenación de los autómatas finitos.

Suponga que tenemos dos máquinas de Turing M1 y M2, con diagramas de

transiciones T1 y T2, respectivamente, y símbolos de cinta del conjunto. Si

queremos desarrollar un diagrama de transiciones para otra máquina que

simule las actividades de M1 seguidas por las de M2, bastaría con eliminar la

designación de parada del estado de parada T1 y la caracteristica de inicio

del estado inicial de T2, y luego dibujar un arco con etiqueta x/x para cada x

en, del antiguo estado de parada de T1 al antiguo estado inicial de T2.

Supongamos que queremos que la maquina compuesta se detenga después

de simular M1, a menos que el símbolo actual, al llegar al estado de parada,

sea z, en cuyo caso nos gustaría que la nueva máquina simulara las acciones

de M2; o supongamos que necesitamos combinar 3 diagramas y controlar el

paso de uno a otro dependiendo del valor del símbolo actual al llegar a cada

uno de los antiguos estados de parada. En este caso re requiere un enlace

más complicado.

Si necesitamos combinar los diagramas de transiciones de varias máquinas

que simule alguna combinación de las máquinas originales. Seguimos los

siguientes pasos:

Elimine la característica de inicio de los estados iniciales de todas las

máquinas, excepto la de aquél donde iniciará la máquina compuesta.

Elimine la característica de detención de los estados de parada de todas las

máquinas e introduzca un nuevo estado de parada que no se encuentre en

ninguno de los diagramas que se combinan.

Para cada uno de los antiguos estados de parada p y cada x en , dibuje un

arco de la siguiente forma:

a).- Si la máquina compuesta debe detenerse al llegar a p con el símbolo

actual x, dibuje un arco con etiqueta x/x de p al nuevo estado de parada.

b).- Si al llegar al estado p con el símbolo actual x, la máquina compuesta

debe transferir el control a la máquina , dibuje entonces un arco con etiqueta

x/z de p al estado q de M, donde .

Mueve la cabeza una celda hacia la derecha.

Encuentra la primera x ala derecha de la celda actual

Encuentra la primera y a la derecha de la celda actual

Encuentra la segunda ocurrencia del símbolo distinto de espacio en blanco

que está a la derecha de la posición inicial de la cabeza.

La Máquina compuesta de las figuras anteriores podría resumirse con el

diagrama compuesto:

donde el nodo A representa la máquina que mueve su cabeza una celda a la

derecha, B la máquina que busca una x y C la máquina que busca una y.

Ejemplo de Maquinas de Turing compuesta:

Otra abreviatura que utilizaremos consiste en aplicar la notación:

4.3 Lenguajes aceptados por una maquina Turing.

Aceptan lenguajes formales que pueden ser generados por una gramática de

tipo 0: recursivamente innumerable. Las máquinas de Turing son los

reconocedores de lenguaje más poderosos que existen.

Lenguajes regulares: las gramáticas (de tipo 3) formales definen un lenguaje

describiendo como se pueden generar las cadenas del lenguaje… Las

gramáticas regulares (aquellos reconocidos por un autómata finito). Son las

gramáticas más restrictivas. El lado derecho de una producción debe

contener un símbolo Terminal y como máximo un símbolo no Terminal.

Máquinas de Turing Deterministas y no Deterministas

La entrada de una máquina de Turing viene determinada por el estado actual

y el símbolo leído, un par [estado, símbolo], siendo el cambio de estado, la

escritura de un nuevo símbolo y el movimiento las acciones a tomar en

función de una entrada. En el caso de que para cada par estado y símbolo

posible exista a lo sumo una posibilidad de ejecución, se dirá que es una

máquina de Turing determinista, mientras que en el caso de que exista al

menos un par [estado, símbolo] con más de una posible combinación de

actuaciones se dirá que se trata de una máquina de Turing no determinista.

La función de transición δ en el caso no determinista, queda definida como

sigue:

¿Cómo sabe una máquina no determinista cuál de las varias actuaciones

tomar? Hay dos formas de verlo: una es decir que la máquina es "el mejor

adivino posible", esto es, que siempre elige la transición que eventualmente

la llevará a un estado final de aceptación. La otra es imaginarse que la

máquina se "clona", bifurcándose en varias copias, cada una de las cuales

sigue una de las posibles transiciones. Mientras que una máquina

determinista sigue un solo "camino computacional", una máquina no

determinista tiene un "árbol computacional". Si cualquiera de las ramas del

árbol finaliza en un estado de aceptación, se dice que la máquina acepta la

entrada.

La capacidad de cómputo de ambas versiones es equivalente; se puede

demostrar que dada una máquina de Turing no determinista existe otra

máquina de Turing determinista equivalente, en el sentido de que reconoce

el mismo lenguaje, y viceversa. No obstante, la velocidad de ejecución de

ambos formalismos no es la misma, pues si una máquina no determinista M

reconoce una cierta palabra de tamaño n en un tiempo O(t(n)), la máquina

determinista equivalente reconocerá la palabra en un tiempo O(2t(n)). Es

decir, el no determinismo permitirá reducir la complejidad de la solución de

los problemas, permitiendo resolver, por ejemplo, problemas de complejidad

exponencial en un tiempo polinómico.

Lenguajes Libres de contexto: Estas gramáticas conocidas también como

gramáticas de tipo 2 o gramáticas independientes del contexto, son las que

generan los lenguajes libres o independientes del contexto. Los lenguajes

libres del contexto son aquellos que pueden ser reconocidos por un autómata

de pila determínistico o no determínistico. Como toda gramática se definen

mediante una cuadrupla G=N, T, S, P), siendo N un conjunto finito de

símbolos no terminales; T un conjunto de símbolos terminales: P un conjunto

finito de producciones; S es el símbolo distinguido o axioma.

Una máquina de Turing se puede comportar como un aceptador de un

lenguaje. Si colocamos una cadena w en la cinta, situamos la cabeza de

lectura/escritura sobre el símbolo del extremo izquierdo de la cadena w y

ponemos en marcha la máquina a partir de su estado inicial. Entonces w es

aceptada si, después de una secuencia de movimientos, la máquina de

Turing llega a un estado final y para. Por tanto w es aceptada. Si qw * w1pw2

para algún estado final p y unas cadenas w1 y w2.

Entonces, se obtiene la siguiente definición:

Sea M = (Q, S , G, q0=q1, B, F, d) una máquina de Turing. Entonces el

lenguaje aceptado por M es: L(M) = {wÎ S*½q1w * w1pw2 para pÎF y wiÎG*}.

Los lenguajes formales que son aceptados por una máquina de Turing son

exactamente aquellos que pueden ser generados por una gramática formal.

El cálculo Lambda es una forma de definir funciones. Las funciones que

pueden se computadas con el cálculo Lambda son exactamente aquellas que

pueden ser computadas con una máquina de Turing.

Estos tres formalismos, las máquinas de Turing, los lenguajes formales y el

cálculo Lambda son formalismos muy disímiles y fueron desarrollados por

diferentes personas. Sin embargo, ellos son todos equivalentes y tienen el

mismo poder de expresión. Generalmente se toma esta notable coincidencia

como evidencia de que la tesis de Church-Turing es cierta, que la afirmación

de que la noción intuitiva de algoritmo o procedimiento efectivo de cómputo

corresponde a la noción de cómputo en una máquina de Turing.

Gramáticas estructuradas por frases:

Parte izquierda de las reglas: combinación de símbolos terminales

y no terminales, con al menos un no terminal.

Parte derecha de las reglas: combinación de símbolos terminales y no

terminales de cualquier longitud (incluso 0).

Las máquinas de Turing aceptan lenguajes estructurados por frases.

La M.T. como generadora de lenguajes.

L={an b2n an, con n mayor o igual a 0}

Entrada:

Cinta1: ...BBB...

Cinta2: ...BBB...

Salida:

Cinta1: ...0000...

Cinta2: ...λ$abba$aabbbbaa$...

Proceso:

El proceso de la maquina es sencillo, consiste en generar 0's en la primera

cinta y su correspondiente lenguaje en la segunda cinta. Este proceso será

cíclico y sin fin, ya que estamos tratando con un generador.

Para ello utilizamos multicinta porque nos facilita de manera considerable el

trabajo.

Ejemplificaciones del funcionamiento de una Máquina de Turing.

Supongamos que tenemos Σ={a,b} y q_f y que representamos los enteros

positivos mediante cadenas solo de “as”. Así el entero “n” estaría

representado por a^n.

Se puede construir la MT que calcule la función f(n,m) = n+m, implementando

la transformación

a^n ba^m en a^(n+m) b

Solución:

Se recorren desde la izquierda todas las as hasta encontrar una “b”, esta se

reemplaza por una “a”, cambiando de estado, en este mismo estado se

recorren todas las “as” a la derecha y cuando se llega a un blanco se

reemplaza por el mismo blanco se deja la cabecera a la izquierda y se

reemplaza la “a” por un blanco para restarle la que adiciono y se mueve hacia

la derecha y se cambia al estado final “q3”.

M=(Q,Σ,Γ,q_0,q_3,B,δ)

Donde la función se define así: