TIPOS DE GRAMATICAS
JERARQUIAS DE CHOMSKY
Para el estudio de este tema es necesario analizar dos tipos de gramáticas de la
clasificación de Chomsky, las regulares y las independientes de contexto, las
reglas permitidas y no permitidas. Tener un conocimiento amplio de las
gramáticas y el lenguaje que se emplea en cada una de ellas, es una
herramienta mas para la realización de los analizadores.
En 1959 Noam Chomsky clasifico las gramáticas en cuatro familias. Las gramáticas
no restringidas, sensibles al contexto, independientes del contexto y las
gramáticas regulares que se conocen como gramáticas de tipo cero, uno, dos y
tres respectivamente. Los lenguajes que resultan de dichas gramáticas también
se identifican con lenguajes de tipo cero, uno, dos y tres. A esta jerarquía de
lenguaje se le conoce como la jerarquía de chomsky.
GRAMÁTICAS Y TIPO DE
LENGUAJES
GRAMATICA
Regular
Independiente del
contexto
Sensible al contexto
Tipo no restringido
TIPO
LENGUAJE QUE GENERA
3 Lenguaje tipo 3 o lenguaje regular
Lenguaje de tipo 2 o lenguaje independiente al
2
contexto
1 Lenguaje tipo 1 lenguaje sensible al contexto.
0 Tipo cero lenguaje no restringido.
GRAMÁTICAS INDEPENDIENTES
DEL CONTEXTO.







A diferencia de las gramáticas regulares, estas gramáticas no tienen
restricciones con respecto a la forma del lado derecho de sus reglas de
reescritura aunque aun se requiere que el lado izquierdo de cada regla sea un no
terminal. La siguiente es una gramática independiente del contexto, pero no es
regular.
S -> zMNz
M -> aMa
M -> z
N -> bNb
N -> z
El termino independiente del contexto refleja que, como el lado izquierdo de
cada regla de reescritura únicamente puede contener un solo no terminal la regla
puede aplicarse sin importar el contexto donde se encuentre dicho no terminal.
Gramática Regular

Gramática Regular: Es aquella gramática cuyas reglas de reescritura tienen las
siguientes restricciones:

El lado izquierdo de cualquier regla de reescritura debe consistir en un solo no
terminal, el lado derecho debe ser un terminal seguido por un no terminal, o un
solo terminal o la cadena vacía
 LA IMPORTANCIA DE LAS GRAMÁTICAS REGULARES
RESIDE EN QUE LOS LENGUAJES GENERADOS POR
ELLAS SON EXACTAMENTE AQUELLOS QUE RECONOCEN
LOS AUTÓMATAS FINITOS.
AUTOMATAS
AUTÓMATAS
La palabra autómata, pretende imitar las funciones de los seres
vivos, especialmente relacionadas con el movimiento, por ejes el
típico robot antropomorfo.
En el campo de los traductores, Procesadores, Compiladores e
interpretes, lo fundamental no es la simulación del movimiento, sino
la simulación de procesos para tratar información.
La información se codifica en cadena de símbolos que se le
presentan a su entrada, produciendo otras tiras o cadenas de
símbolos a su salida.
Los símbolos de entradas son secuenciales y la salida no solo
depende de la entrada, sino de toda la secuencia recibida
anteriormente.
ESTADO DE UN AUTÓMATA: Es toda la información necesaria en un
momento dado, para poder deducir, dado un símbolo de entrada en
ese momento, cuál será el símbolo de salida.
Arquitectura de un autómata Finito
(AF)
Un autómata finito es una estructura matemática que representa un sistema o
máquina abstracta cuya arquitectura puede verse en la figura
La cinta de entrada (que se extiende infinitamente hacia la derecha) está dividida en
celdas, cada una de las cuales es capaz de almacenar un sólo símbolo de un
cierto alfabeto. La máquina es capaz de leer los símbolos de esta cinta de
izquierda a derecha por medio de un cabezal de lectura.
Cada vez que se lee un símbolo, el cabezal de lectura se mueve a la siguiente celda a
la derecha y la máquina efectúa un cambio de estado o transición. Esta
transición está determinada por el mecanismo de control (que contiene un
número finito de estados), programado para conocer cual debe ser el nuevo
estado, que dependerá de la combinación del estado actual y el símbolo de
entrada leído.
Los autómatas finitos pueden considerarse como mecanismos aceptadores o
reconocedores de palabras. De manera informal decimos que un autómata finito
aceptará una palabra de entrada si, comenzando por un estado especial llamado
estado inicial y estando la cabeza de lectura apuntando al primer símbolo de la
cadena, la máquina alcanza un estado final o de aceptación después de leer el
último símbolo de la cadena.
Autómatas Finitos deterministas
Un autómata finito determinista (AFD) se define como una quintuplaM = (Q; V; δ; q0;
F),
donde:
El nombre “determinista" viene de la forma en que está definida la función de
transición: si en un instante t la máquina está en el estado q y lee el símbolo a
entonces, en el instante siguiente t + 1 la máquina cambia de estado y sabemos
con seguridad cual es el estado al que cambia,
que es precisamente δ(q; a).
Autómatas Finitos deterministas
La función de transición de un AFD se puede representar de dos formas: mediante
una tabla de transición o mediante un diagrama de transición.
Ejemplo: Supongamos que tenemos el autómata finito determinista dado por
M = ({q0, q1, q2}, {0, 1}, δ, q0, {q1})
donde la función δ : {q0, q1, q2} x {0, 1} -> {q0; q1; q2} viene dada por
δ(q0, 0) = q0
δ(q1, 0) = q0
δ(q2, 0) = q2
δ(q0, 1) = q1
δ(q1, 1) = q2
δ(q2, 1) = q1
La tabla de transición correspondiente sería:
y el diagrama de transición
Autómatas finitos no deterministas
Un autómata finito no determinista (AFND) es una quíntupla M = (Q; V;Δ; q0; F)
donde todos los componentes son como en los AFDs, excepto la función de transición
que se define ahora como:
donde P(Q) denota el conjunto de las partes de Q (o conjunto potencia 2Q).
El hecho de que el condominio de la función de transición sea P(Q) es lo que
añade esta característica de “no determinismo": a partir del estado actual y
del símbolo actual de entrada no se puede determinar de forma exacta cuál
sería el estado siguiente. Por ejemplo, podemos tener Δ(q; a) = {q1, q2,..qm}
y esto indica que dado el estado actual q y el símbolo de entrada a, el
estado siguiente puede ser cualquier estado entre q1 y qm: También puede
darse el caso de que Δ(q; a) = Ø , lo que indica que el estado siguiente no
está definido.
Autómatas finitos no deterministas
Máquina de Moore
Se define como la 6-tupla {Q,∑,S,δ, λ,q0} donde:
Q: Es el conjunto finito de estados.
∑: Es el alfabeto de entrada.
S: Es el alfabeto de salida.
δ : Función de transición Q × ∑ → Q.
λ : Función de Q a S, dado q nos arroja una s donde s ∈ S y q ∈ Q.
q0: Estado inicial.
Nuestra máquina comienza en su estado inicial q0, la función de salida nos entrega un
símbolo s cada vez que llegamos a un estado, la función de transición lee un
elemento de la cadena de entrada e indica el nuevo estado que adoptaremos,
puede ser el mismo, depende del símbolo leído y del estado actual.
Máquina de Moore
Un ejemplo es:
Si introducimos la cadena 11001 la máquina arroja la secuencia de datos
baabba. El primer símbolo siempre será el mismo ya que siempre que
comenzamos a analizar una cadena partimos del estado inicial.
Máquina de Mealy
Máquina de Mealy También se define como una 6-tupla {Q, ∑, S, δ, λ , q0}
donde:
Q: Es el conjunto finito de estados.
∑ : Es el alfabeto de entrada.
S: Es el alfabeto de salida.
δ : Función de transición Q × ∑ → Q.
λ : Función de salida Q × ∑ → S, λ(qi, a) → s donde s ∈ S, q ∈ Q y a ∈ ∑.
q0: Estado inicial.
Máquina de Mealy
Un ejemplo de una Máquina de Mealy es:
A diferencia de la Máquina de Moore se excluye el primer elemento en todas
las cadenas de salida, es decir, si introducimos la misma cadena que en el
ejemplo anterior 11001 obtenemos como resultado aabba y podemos
observar la equivalencia de ambas máquinas.
Máquina de Turing
 La idea de una Máquina que pudiera seguir un conjunto de pasos que describen
cualquier sentencia matemática, es decir que puede ser descrita por un algoritmo fue
introducida por primera vez por Alan Turing en 1936
 Una Máquina de Turing es solamente un concepto abstracto y no realmente
una máquina como posiblemente la imaginemos
 Imaginemos que nuestra máquina tiene un conjunto finito de estados (Q),
tiene uno y solo un estado inicial (q0) el cual siempre es el primero cuando la
máquina comienza a trabajar, puede tener uno o más estados finales (F) que le
indican a la máquina cuando parar . Cambia de un estado a otro y regresa a
ellos cuantas veces es necesario hasta llegar a uno de los estados finales y haber
recorrido todos los elementos de una cadena de entrada (E). También tiene un
cabezal de lectura y escritura con el cual puede obtener datos y escribirlos en
una cinta que idealmente es infinitamente larga, la cual está dividida en casillas
o celdas donde solo puede contener uno y sólo uno de los símbolos de entrada.
Máquina de Turing
Su forma de trabajo es la siguiente:
 Según el estado de la máquina y el valor leído de la cadena de entrada escrita
en la cinta (un símbolo por celda), escribe un nuevo símbolo en esa casilla,
mueve la cinta a la derecha o a la izquierda (una celda a la vez) y cambia de
estado.
 Nuevamente lee el símbolo de la celda actual y según su nuevo estado repetiría
el mismo proceso hasta recorrer todos los símbolos de entrada o situarse en un
estado terminal.
 Existe una función de transición () o tabla de transición que nos indica, según
el estado de la máquina y el valor leído, el símbolo a ser escrito y el nuevo estado
que se debe adoptar así como el movimiento de la cinta (derecha o izquierda)
que se va a realizar.
Máquina de Turing
Ahora podemos definir formalmente una Máquina de Turing (MT) como una
7-tupla de la forma: MT = {Q, ∑, Г, δ, q0, B, F}
Q: Es el conjunto finito de estados, son todos y cada uno de los posibles
estados en que puede estar nuestra máquina.
∑ : Es un conjunto finito de símbolos de entrada. Son todos aquellos elementos
que va a recibir nuestra máquina para su lectura.
Г : Es el conjunto finito de símbolos que puede reconocer nuestra máquina,
es decir, el alfabeto, donde ∑ ∈ Г.
δ : Es la función de transición δ (qi,σ) → (qk,γ,R|L), también puede ser
representada por una tabla llamada Tabla de transición. Y nos indica la función
de nuestra máquina:
Máquina de Turing

La función δ recibe como parámetros el estado qi(qi ∈ Q) en el que se
encuentra actualmente la maquina y un símbolo σ(σ ∈ ∑) leído de la cadena de
entrada.

Tal combinación de parámetros nos va a dar un nuevo estado (qk) y escribirá un
símbolo γ(γ ∈ Г) en la celda donde recién acaba de leer el símbolo.

Por ´ultimo se moverá la izquierda (R) o a la derecha (R) una sola celda a
la vez y se repetirá el mismo proceso ahora con los nuevos valores.


B: Es el símbolo en blanco, indica que la celda está vacía.
F: Es el conjunto de estados finales.
Máquina de Turing
A simple vista parece un modelo sencillo, pero su poder es tal que cualquier
modelo computacional o algoritmo existente puede ser modelado por una
Máquina de Turing.
Podemos decir que cualquier solución a un problema que pueda ser representada
por una Máquina de Turing está haciendo una computación.
Si una máquina imprime dos tipos de símbolos, donde el primer tipo (llamadas
figuras) consiste íntegramente en 1 y 0 y el segundo tipo serán llamados símbolos
de la segunda especie entonces podemos llamar a esa maquina computadora
Descargar

Diapositiva 1