Presentado por: Edward Alberto Silva bolvar
Tutor: Vctor Fernando Canon Rodrguez
Grupo: 301405_8
es un tipo de lenguaje formal que satisface las siguientes propiedades:
Los lenguajes ms sencillos que se considerarn son los lenguajes regulares, es
decir, los que se pueden generar a partir de los lenguajes bsicos, con la aplicacin
de las operaciones de unin, concatenacin y * de Kleene un nmero finito de
veces.
Puede ser reconocido por:
un autmata finito determinista
un autmata finito no determinista
un autmata de pila
un autmata finito alterno
una mquina de Turing de solo lectura
Es generado por:
una gramtica regular
una gramtica de prefijos
Es descrito por:
una expresin regular
Ejemplo 2
En un acuario de Miami se entrenan las capacidades intelectuales de los delfines en
cautiverio y tiene especial importancia los resultados que tiene uno de los ejemplares quien
ha aprendido a reconocer cantidades pares a partir de imgenes de peces, llegando a
distinguir cuando hay un nmero par o no de peces en la imagen. Muestre que las imgenes
de cantidad de peces pares es un lenguaje regular que puede percibir el delfn.
Se define a cada pez de las imgenes con la letra p minscula y se ve que para las
imgenes pares puede definirse las siguientes producciones de una gramtica regular:
Flecha pp o pp i.gif
Por ende, se trata de un LR
es una secuencia de caracteres que forma un patrn de bsqueda, principalmente
utilizada para la bsqueda de patrones de cadenas de caracteres u operaciones de
sustituciones. Por ejemplo, el grupo formado por las cadenas , Hndel y Haendel se
describe con el patrn "H(a||ae)ndel". La mayora de las formalizaciones
proporcionan los siguientes constructores: una expresin regular es una forma de
representar los lenguajes regulares (finitos o infinitos) y se construye
utilizando caracteres del alfabeto sobre el cual se define el lenguaje.
Unos ejemplos simplificados:
<? am // este es nuestro patrn. Si lo comparamos con:
am // coincide
panorama // coincide
ambicin // coincide
campamento // coincide
mano // no coincide
?>
Se trata sencillamente de ir cotejando un patrn (pattern) -que en este ejemplo es la
secuencia de letras 'am'- con una cadena (subject) y ver si dentro de ella existe la
misma secuencia. Si existe, decimos que hemos encontrado una coincidencia
(match, en ingls).
Autmata finito (mquina de estado finito). Es un modelo computacional que
realiza cmputos en forma automtica sobre una entrada para producir una salida.
Este modelo est conformado por un alfabeto, un conjunto de estados y un conjunto
de transiciones entre dichos estados. Su funcionamiento se basa en una funcin de
transicin, que recibe a partir de un estado inicial una cadena de caracteres
pertenecientes al alfabeto (la entrada), y que va leyendo dicha cadena a medida que
el autmata se desplaza de un estado a otro, para finalmente detenerse en un estado
final o de aceptacin, que representa la salida.
Definicin formal
Formalmente, un autmata finito es una 5-tupla (Q, , q0, , F) donde
Q\, es un conjunto finito de estados;
\Sigma \, es un alfabeto finito;
q_{0}\in Q es el estado inicial;
\delta \colon Q\times \Sigma \to Q es una funcin de transicin;
F\subseteq Q es un conjunto de estados finales o de aceptacin.
Un autmata finito determinista (abreviado AFD) es un autmata finito que
adems es un sistema determinista; es decir, para cada estado en que se encuentre
el autmata, y con cualquier smbolo del alfabeto ledo, existe siempre no ms de
una transicin posible desde ese estado y con ese smbolo.
Autmata finito determinista que reconoce el lenguaje regular conformado
exclusivamente por las cadenas con un nmero par de ceros y un nmero par de
unos.
Autmata finito no determinista. Es el autmata finito que tiene transiciones
vacas o que por cada smbolo desde un estado de origen se llega a ms de un
estado destino.
Los AFND son definiciones no tan deseables dentro de los lenguajes regulares
porque dificultan su implementacin tanto mecnica como informtica; aunque en
la mayora de las transformaciones a lo interno de los LR (expresiones regulares a
AF, gramticas regulares a AF) conducen a AFND. Los AFND, por tanto, son
imprescindibles en el anlisis lexicogrfico y el diseo de los lenguajes de
programacin.
El ejemplo siguiente muestra un AFND M, con un alfabeto binario que determina si
la entrada contiene un nmero par de 0s o un nmero par de 1s. Entonces M = (Q,
, T, s0, F) donde:
= {0, 1},
Q = {s0, s1, s2, s3, s4},
E({s0}) = { s0, s1, s3 }
F = {s1, s3}, y
La funcin de transicin T puede ser definida por esta tabla de transicin de
estados:
