Automatas_aritameticas.docx

1) L={<=∞xϵ{a,b}* |x es palíndromo} ϵ a b aa bb aba abba aaaaaa babbab bbbbbb baaaab aabbaa bbababb aababaa

Nota Es lo mismo de derecha e izquierda, izquierda y derecha

2) (aab|b)* (ab*a)*

S ->SS|SSS 2 S-> (S)*|ϵ 3 S->S* 4 S->ab|b|a 5 S->| S->SS S->(S)*S S->(SSS)*S S->(SSSS)*S S->(SSSS)*(S)* S->(SSSS)*(SS)* S->(SSSS)*(S*S)* S->(SSSS)*(ab*S)* S->(SSSS)*(ab*a)* S->(aSSS)*(ab*a)* S->(aabSS)*(ab*a*)* S->(aab|b)*(ab*a*)*

(1) (2) (1) (1) (2) (1) (3) (4) (4) (4) (4) (5)

3) todas las expresiones aritméticas parentizadas de x E -> E + E E -> E – E E -> E * E E -> E / E E -> (E) E -> x

4) Notación de Backus-Naur La notación de Backus-Naur, también conocida por sus denominaciones inglesas Backus-Naur form (BNF), Backus-Naur formalism o Backus normal form, es un metalenguaje usado para expresar gramáticas libres de contexto: es decir, una manera formal de describir lenguajes formales. El BNF se utiliza extensamente como notación para las gramáticas de los lenguajes de programación de la computadora, de los sistemas de comando y de los protocolos de comunicación, así como una notación para representar partes de las gramáticas de la lengua natural (por ejemplo, el metro en la poesía de Venpa). La mayoría de los libros de textos para la teoría o la semántica del lenguaje de programación documentan el lenguaje de programación en BNF. Algunas variantes, tales como la Augmented Backus-Naur Form (ABNF) y la Extended Backus–Naur Form (EBNF), tienen su propia documentación. Las gramáticas de tipo 2 (que incluyen a las gramáticas de tipo 3) tienen métodos alternativos útiles para desplegar las producciones. Una alternativa que se encuentra con frecuencia es la notación BNF (forma Backus-Naur). Se sabe que los lados izquierdos de todas las producciones en una gramática de tipo 2 son símbolos no terminales únicos. Para cada uno de tales símbolos w, se combina todas las producciones que tienen a w como lado izquierdo. El símbolo w permanece a la izquierda, y todos los lados derechos asociados con w son enumerados juntos, separados por el símbolo |. El símbolo relacional se reemplaza por el símbolo ::=. Por último, los símbolos no terminales, cuando aparezcan, serán encerrados entre paréntesis agudos < >. Esto tiene la ventaja adicional de que los símbolos no terminales pueden tener espacios dentro de ellos. Así, <palabra1 palabra2> muestra que la cadena entre paréntesis debe considerarse como una "palabra", no como dos palabras. Es decir, se puede utilizar el espacio como una "letra" conveniente y legítima en una palabra, mientras que se utilice los paréntesis agudos para delimitar las palabras.

Ejemplo 1. En la notación BNF, las producciones del ejemplo 1 de la sección 10.1 aparecen como sigue:

<sujeto> <predicado>

::= ::= ::= ::= ::=

<sujeto> <predicado> Juan | Julia maneja | corre descuidadamente | rápido | frecuentemente

Ejemplo 2. En la notación BNF, las producciones del ejemplo 2 de la sección 10.1 aparecen como sigue: ::= a<w> <w> ::= bb<w> | c Observe que el lado izquierdo de una producción puede aparecer tambén en una de las cadenas del lado derecho. Así, en la segunda línea del ejemplo 2, <w> aparece a la izquierda, y aparece en la cadena bb<w> de la derecha. Cuando esto ocurre, se dice que la producción correspondiente w bbw es recursiva. Si una producción recursiva tiene a w como lado izquierdo, la producción es normal si w aparece sólo una vez en el lado derecho y es el símbolo del extremo derecho. En el lado derecho también pueden aparecer otros símbolos no terminales. La producción recursiva w bbw del ejemplo 2 es normal. Observe que cualquier producción recursiva que aparezca en una gramática (regular) de tipo 3 es normal, por la definición del tipo 3. Ejemplo 3. La notación BNF se utiliza con frecuencia para especificar los lenguajes de programación reales. PASCAL y muchos otros lenguajes tenían dadas sus gramáticas en BNF inicialmente. En este ejemplo se considerará un pequeño subconjunto de la gramática de PASCAL. Este subconjunto describe la sintaxixs de los números decimales y se puede ver como una minigramática cuyo lenguaje correspondiente consta precisamente de todos los números decimales formados de manera adecuada. Sea S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, .}. Sea V la unión de S con el conjunto N = {número-decimal, fracción-decimal, entero-sin-signo, dígito}. Así, sea G la gramática con conjuntos de símbolos V y S, con símbolo inicial "número decimal" y con las producciones dadas en forma BNF como sigue: ::= <entero-sin-signo> | | ::= <entero-sin-signo> <entero-sin-signo> ::= | <entero-sin-signo> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

La figura 10.4 muestra un árbol de deducción, en esta gramática, del número decimal 23.14. Observe que el enunciado BNF número 3 es recursivo en la segunda parte de su lado derecho. Es decir, la producción "entero-sin-signo dígito entero-sin-signo" es

recursiva y también es normal. En general, se sabe que muchas gramáticas diferentes pueden producir el mismo lenguaje. Si se reemplaza la línea anterior número 3 con la línea 3'. <entero-sin-signo> ::= | <entero-sin-signo> se tendría una gramática diferente que produce exactamente el mismo lenguaje, a saber, los números decimales formados de manera correcta. Sin embargo, esta gramática contiene una producción recursiva que no es normal.

Figura 10.4 Ejemplo 4. Como en el ejemplo 3, se proporcionará una gramática que especifique una parte de varios lenguajes de programación reales. En estos lenguajes, un identificador (un nombre para una variable, función, subrutina, etcétera) debe estar compuesto por letras y dígitos y debe comenzar con una letra. La siguiente gramática, con las producciones dadas en BNF, tiene precisamente estos identificadores como su lenguaje. G = (V, S, identificador, ) N = {identificador, resto, dígito, letra} S = {a, b, c, . . . , z, 0, 1, 2, 3, . . . , 9}, V=NUS ::= | ::= | | | ::= a | b | c . . . | z ::= 0 | 1 | 2 | 3 | 4 | 5 | 6| 7 | 8 | 9