AUTÓMATA PILA

AUTOMATA DE PILAS

Indice:

1. Funcionamiento de un A.P

2. Diseño de un A.P

3. Definición Formal de un A.P

4. Lenguaje Reconocido por un A.P

5. Forma Normal de Chomsky

6. Forma Normal de Greibanch

1.- FUNCIONAMIENTO DE A.P

Los autómatas de pila, en forma similar a como se usan los autómatas finitos, también se pueden utilizar para aceptar cadenas de un lenguaje definido sobre un alfabeto A. Los autómatas de pila pueden aceptar lenguajes que no pueden aceptar los autómatas finitos. Un autómata de pila cuenta con una cinta de entrada y un mecanismo de control que puede encontrarse en uno de entre un número finito de estados. Uno de estos estados se designa como estado inicial, y además algunos estados se llaman de aceptación o finales. A diferencia de los autómatas finitos, los autómatas de pila cuentan con una memoria auxiliar llamada pila. Los símbolos (llamados símbolos de pila) pueden ser insertados o extraídos de la pila, de acuerdo con el manejo last-in-first-out (LIFO). Las transiciones entre los estados que ejecutan los autómatas de pila dependen de los símbolos de entrada y de los símbolos de la pila. El autómata acepta una cadena x si la secuencia de transiciones, comenzando en estado inicial y con pila vacía, conduce a un estado final, después de leer toda la cadena x.1​

2.- DISENO DE A.P

3.- DEFINICIÓN FORMAL DE A.P

Formalmente, un autómata con pila puede ser descrito como una séptupla               {\displaystyle M=(S,\Sigma ,\Gamma ,\delta ,s,Z,F)}donde:

·         {\displaystyle S}  es un conjunto finito de estados;

·         {\displaystyle \Sigma }  y {\displaystyle \Gamma }  son alfabetos (símbolos de entrada y de la pila respectivamente);

·         {\displaystyle \delta :S\times (\Sigma \cup \{\epsilon \})\times \Gamma \rightarrow {\mathcal {P}}(S\times \Gamma ^{*})}

·         {\displaystyle s\in S}  es el estado inicial;

·         {\displaystyle Z\ \in \Gamma }  es el símbolo inicial de la pila;

·         {\displaystyle F\subseteq S}  es un conjunto de estados de aceptación o finales;

La interpretación de  , con  , y   es la siguiente:

Cuando el estado del autómata es {\displaystyle q} , el símbolo que la cabeza lectora está inspeccionando en ese momento es {\displaystyle a} , y en la cima de la pila nos encontramos el símbolo {\displaystyle b} , se realizan las siguientes acciones:

·         Si {\displaystyle a\in \Sigma } , es decir no es la cadena vacía, la cabeza lectora avanza una posición para inspeccionar el siguiente símbolo.

·         Se elimina el símbolo {\displaystyle b}  de la pila del autómata.

·         Se selecciona un par {\displaystyle (q_{i},\gamma _{i})}  de entre los existentes en la definición de {\displaystyle \delta (q,a,b)} , la función de transición del autómata.

·         Se apila la cadena {\displaystyle \gamma _{i}=c_{1}c_{2}\ldots c_{k}} , con {\displaystyle c_{i}\in \Gamma }  en la pila del autómata, quedando el símbolo {\displaystyle c_{k}}  en la cima de la pila.

·         Se cambia el control del autómata al estado {\displaystyle q_{i}}

4.- LENGUAJE RECONOCIDO POR A.P 

5.- FORMA NORMAL DE CHOMSKY

OBJETIVO

Comprender la manera en que podemos convertir una gramática independiente del contexto a una gramática de la Forma Normal de Chomsky.

JUSTIFICACIÓN

Las gramáticas tienen ciertas similitudes, pero cuando no es así es necesario realizar una serie de pasos los cuales nos permitan obtener dos gramáticas diferentes y que lleguen al mismo resultado.

INTRODUCCIÓN

Las gramáticas se pueden expresar de diferentes formas, en ocasiones podemos llegar al mismo resultado utilizando gramáticas que difieren en su estructura, una norma para estandarizar las gramática es la Forma Normal de Chomsky.

CONTENIDO

Teorema 2.4

Si L es un lenguaje independiente del contexto que no contiene la cadena vacía, entonces existe una gramática G independiente del contexto tal que L(G)=L y el lado derecho de cualquier regla de reescritura en G consiste en un solo terminal o exactamente dos no terminales. Se dice que una gramática cuyas reglas de reescritura se adhieren a las restricciones del teorema 2.4 tiene la

FORMA NORMAL DE CHOMSKY

(FNC o CNF), llamada así en honor a Noam Chomsky. Por ejemplo la siguiente gramática cuyo símbolo inicial es S tiene la forma normal de Chomsky.

S->XM

M->SY

X->x

Y->y

6.- FORMA NORMAL DE GREIBACH

En la teoría del lenguaje formal , una gramática sin contexto está en forma normal de Greibach (GNF) si los lados derechos de todas las reglas de producción comienzan con un símbolo terminal , seguido opcionalmente por algunas variables. Un formulario no estricto permite una excepción a esta restricción de formato para permitir que la palabra vacía(epsilon, ε) sea un miembro del lenguaje descrito. La forma normal fue establecida por Sheila Greibach y lleva su nombre.

Más precisamente, una gramática libre de contexto está en forma normal de Greibach, si todas las reglas de producción son de la forma: {\ displaystyle S \ to \ varepsilon}dónde {\ displaystyle A} es un símbolo no terminal ,{\ displaystyle a} es un símbolo terminal, {\ displaystyle A_ {1} A_ {2} \ ldots A_ {n}}  es una secuencia (posiblemente vacía) de símbolos no terminales que no incluyen el símbolo de inicio, {\ displaystyle S} es el símbolo de inicio, y ε es la palabra vacía . ^[1]Observe que la gramática no tiene recursiones de izquierda .

Toda gramática sin contexto puede ser transformada en una gramática equivalente en la forma normal de Greibach. ^[2] Existen varias construcciones. Algunos no permiten la segunda forma de regla y no pueden transformar gramáticas sin contexto que pueden generar la palabra vacía. Para una construcción de este tipo, el tamaño de la gramática construida es O (n ⁴ ) en el caso general y O (n ³ ) si ninguna derivación de la gramática original consiste en un solo símbolo no terminal, donde n es el tamaño de la gramática original.