Aplicacion en automatas

INDICE

Aplicación de las Expresiones Regulares: problema y desarrollo de solución 4

Aplicación de los Autómatas: problema y desarrollo de solución 6

Aplicación de las Gramáticas: problema y desarrollo de solución 8

Fuentes de consulta 10

Aplicación de las Expresiones Regulares: problema y desarrollo de solución

Una expresión regular es una forma de representarcierto tipo de lenguajes sobre un determinado alfabeto. Son exactamente los aceptados por los autómatas de estado finito.

Dado un alfabeto Σ, las expresiones regulares sobre Σ y los conjuntos denotados por ellas se definen recursivamente como sigue:

1. El conjunto vacío es una expresión regular que denota al lenguaje ∅.
2. La cadena vacía ε es una expresión regular que denota al lenguaje {ε}.3. Cualquier símbolo a ∈ Σ es una expresión regular que denota al lenguaje {a}.
4. Si r y s son expresiones regulares denotando los lenguajes L(r) y L(s) respectivamente, entonces, r ⋅ s (o rs) es una expresión regular que denota al lenguaje L(r) ⋅ L(s).
5. Si r y s son expresiones regulares denotando los lenguajes L(r) y L(s) respectivamente, entonces, r + s es una expresión regular quedenota al lenguaje L(r) ∪ L(s).
6. Si r es una expresión regular denotando al lenguaje L(r), entonces, r* es una expresión regular que denota al lenguaje L(r)*.
7. Sólo son expresiones regulares las que pueden obtenerse mediante la aplicación de las reglas anteriores.
La precedencia de los operadores es: * > ⋅ > +.

EJEMPLOS DE APLICACIÓN:
Ejemplo: Sean los lenguajes A = {0,1}, B ={a,b,c}, C= {1,2}, obtener:

1. (BC) U A
= {a,b,c} {1,2} U {0,1}
= {a1,a2,b1,b2,c1,c2} U {0,1}
= {a1,a2,b1,b2,c1,c2,0,1}

2. A*
= {0,1}* = {0,1}0 U {0,1}1 U {0,1}2 U {0,1}3 U ...
= { Î } U {0,1} U {0,1}{0,1} U {0,1}{0,1}{0,1} U ...
= { Î,0,1} U {00,01,10,11} U {000,001,010,011,100,101,110,111}U...
= { Î,0,1,00,01,10,11,000,001,010,011,100,101,110,111,...}

3. (C U A)+
= ( {1,2} U {0,1} )+= {1,2,0}+ = {0,1,2}+
= {0,1,2}1 U {0,1,2}2 U {0,1,2}3 U ...
= {0,1,2} U {0,1,2}{0,1,2} U {0,1,2}{0,1,2}{0,1,2} U ...
= {0,1,2} U {00,01,02,10,11,12,20,21,22} U ...
= {0,1,2,00,01,02,10,11,12,20,21,22,000,001,002,...,210,221,222,... }

4. Representar en el lenguaje JavaScript la expresión regular que comprendan todos los números naturales:
(ʎ | +)(<digito><digito>*.<digito>*<digito>)

Aplicación de los Autómatas: problema y desarrollo de solución
Los autómatas Finitos son un conjunto de símbolos que constituyen un vocabulario que posee un conjunto finito de estados, existe un estado inicial y un conjunto de estados finales.
Un autómata finito (AF) o máquina de estado finito es un modelo matemático que realiza cómputos en forma automática sobre unaentrada 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 función de transición, 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 autómata se desplaza de un estado a otro,para finalmente detenerse en un estado final o de aceptación, que representa la salida.
La finalidad de los autómatas finitos es la de reconocer lenguajes regulares, que corresponden a los lenguajes formales más simples según la Jerarquía de Chomsky.

EJEMPLOS DE APLICACIÓN:
1. Construir un autómata finito según la siguiente expresión regular: b*(ab*ab*a)*.

2. Construir un autómata finitopara la siguiente expresión regular: b* U b+(ab+)*.

3. Construir un autómata finito determinista que acepta el lenguaje L {0, 1}*, definido
L = {w ∈ {0, 1}*: el número de 0′s es par y el número de 1′s es múltiplo de 3}

Aplicación de las Gramáticas: problema y desarrollo de solución
La gramática es un ente formal para especificar, de manera finita, el conjunto de cadenas de símbolos que...