CENTRO
UNIVERSITARIO UAEM
ATLACOMULCO
LICENCIATURA EN
INGENIERÍA EN COMPUTACIÓN
NOMBRE DEL
DOCENTE:
INGENIERO.
HÉCTOR CABALLERO HERNÁNDEZ
NOMBRE MATERIA:
AUTÓMATAS Y LENGUAJES FORMALES
NOMBRE DE LA
ALUMNA:
HEIVILINA PÉREZ ARIAS
GRUPO:
ICO-19
TURNO:
MATÚTINO
TRABAJO
A ENTREGAR:
* GRAMÁTICA GENERATIVA DE CHOMSKY
* FORMA
NORMAL DE CHOMSKY
* AUTÓMATAS CON TRANSICIONES DE CERRADURA
* AUTÓMATA DE PILA
FECHA
DE ENTREGA:
24 DE MARZO DE 2015.
INDICE
I.- GRAMÁTICA GENERATIVA
DE CHOMSKY………………………………………….....I
I.I.- DESCRIPCIÓN DE LA GRAMÁTICA GENERATIVA DE
CHOMSKY…………...I
I.II.-COMPONETES DE LA GRAMÁTICA
GENERATIVA DE CHOMSKY…………...I
II.- FORMA NORMAL
DE CHOMSKY ……………………….....…………………………...II
II.I.-EXPRESIÓN DE LA GRAMÁTICA EN LA
FORMA NORMAL DE CHOMSKY...II
III.- AUTÓMATA CON TRANSICIONES DE CERRADURA……………………………...III
III.I.-EJEMPLO DE UN AUTÓMATA
FINITO CON TRANSICIÓN DE CERRADURA..III
IV.- AUTÓMATAS A PILA ………………………..............…………………………………..IV
IV. I.- DEFINICIÓN DE
AUTÓMATA A PILA …………………....…………………...IV
IV.II.- NOTACIÓN GRÁFICA
PARA LOS AUTÓMATAS A PILA…………….…........V
IV.III.- REPRESENTACIÓN
DE AUTOMATA DE PILA……………….....……………V
IV.IV.- DEFINICIÓN DE
AUTÓMATA A PILA DETERMINISTA….………………...VI
REFERENCIAS BIBLIOGRÁFICAS…………………………………………………….......VI
INTRODUCCIÓN
En el presente
documento se hablara de algunos temas que son pertenecientes a lo que es la
asignatura de Autómatas y Lenguajes Formales que son los siguientes:
* GRAMÁTICA GENERATIVA DE CHOMSKY
* FORMA NORMAL DE CHOMSKY
* AUTÓMATAS CON TRANSICIONES DE CERRADURA
* AUTÓMATA DE PILA
La gramática generativa, formulada por Noam Chomsky se desenvuelve en
base a la teoría matemática de la información y de la lógica matemática en
general.
Como ya conocemos,
existen gramáticas de muy diferentes formas que generan un mismo lenguaje. El
hecho de no restringir la forma de las reglas de tipo 2 tiene interés en los
casos en que se desea diseñar una gramática para un lenguaje dado. Sin embargo,
cuando se desea desarrollar demostraciones de ciertas propiedades de los
lenguajes incontextuales o se desea desarrollar algoritmos eficientes que
operen sobre gramáticas incontextuales, interesa imponer ciertas restricciones
en las formas de las reglas de la gramática. Para ello se introducen las
definiciones y los algoritmos de obtención de las formas normales para las
gramáticas incontextuales.
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áticas es la Forma Normal de
Chomsky.
De igual manera que
los lenguajes regulares se pueden representar mediante autómatas finitos
deterministas, los lenguajes independientes del contexto tienen su
correspondencia en otro tipo de dispositivo: el Autómata a Pila (AP).
Lo que se menciona
anteriormente es parte de lo que se desarrolla en este escrito, que son temas
pertenecientes a la materia de autómatas y lenguajes formales.
I.-
GRAMÁTICA GENERATIVA DE CHOMSKY
Noam Chomsky creó la
gramática generativa, es un sistema de análisis del lenguaje que situó la
sintaxis en el centro de la investigación lingüística y con la que cambió por
completo la perspectiva, los programas y métodos[1] de investigación en el
estudio del lenguaje, actividad que elevó definitivamente a la categoría de
ciencia moderna. Su lingüística es una teoría de la adquisición individual del
lenguaje y una explicación de las estructuras y principios más profundos del
lenguaje. Postuló el innatismo y la autonomía de la gramática (sobre los otros
sistemas cognitivos), así como la existencia de un «órgano del lenguaje» y de
una gramática universal. Se opuso con dureza al empirismo filosófico y
científico y al funcionalismo, en favor del racionalismo cartesiano. Todas
estas ideas chocaban frontalmente con las sostenidas tradicionalmente por las
ciencias humanas, lo que concitó adhesiones y críticas apasionadas, que le
embarcaron en numerosas controversias, en la historia científica de los últimos
tiempos, lo que le ha acabado convirtiendo en uno de los autores más citados y
también más respetados.
Una
gramática generativa debería distinguirse de las gramáticas tradicionales, que
se caracterizan por su carácter prescriptivo y de otros enfoques descriptivos,
como las vertientes que se inscriben dentro de la gramática funcional.
En
la mayoría de los casos, una gramática generativa debería ser capaz de generar
una infinita cantidad de construcciones sintácticas a partir de un número
limitado de reglas y unidades. Esta propiedad es conocida como recursividad. En
la actualidad, se postula que el lenguaje humano es el único sistema de
comunicación natural con tal propiedad: evidentemente, la capacidad del cerebro
humano es finita, pero no así las oraciones que puede generar e interpretar.
I.I.- DESCRIPCIÓN DE LA GRAMÁTICA GENERATIVA DE
CHOMSKY
La gramática es una descripción explícita del
conocimiento (de la competencia) del hablante-oyente ideal.
Esta gramática es “generativa”
en el sentido de que permite “generar” un conjunto infinito de oraciones en una
lengua particular.
El “conocimiento de la gramática” que posee todo
hablante-oyente ideal hace referencia al
conocimiento de las reglas que todos los hablantes nativos tienen de su propia
lengua. Ejemplo: analfabeto/lingüista.
I.II.-
COMPONETES DE LA GRAMVTICA GENERATIVA DE CHOMSKY
- Componente sintáctico
(generativo: produce O gramaticales)
- Componente fonológico
- Componente semántico
Los otros dos componentes tienen un
carácter interpretativo.
El componente fonológico provee la
representación fonética de las
oraciones.
El componente semántico provee la
representación conceptual de las
oraciones.
[2]II.- FORMA NORMAL DE CHOMSKY
Completamos el estudio sobre las
simplificaciones gramaticales demostrando que todo LIC no vacío sin ε tiene una
gramática G en la que todas las producciones tienen una de las dos
formas siguientes:
1. A→BC, donde A, B y C son
variables, o
2. A→a, donde A es una variable y a es un
símbolo terminal.
Además, G no contiene
símbolos inútiles. Una gramática así se dice que está en la forma normal de Chomsky, o FNC.
II.I.- EXPRESIÓN DE
LA GRAMÁTICA EN LA FORMA NORMAL DE CHOMSKY
Para expresar una gramática en la
forma normal de Chomsky, partimos de una que satisfaga las restricciones; es
decir, la gramática no contiene producciones-ε, ni producciones unitarias ni
símbolos inútiles. Toda producción de dicha gramática es de la forma A→a, que es una forma permitida por la FNC, o tiene un
cuerpo de longitud 2 o superior. Nuestras tareas son entonces:
a) Conseguir que todos los cuerpos
de longitud 2 o superior estén formados sólo por variables.
b) Descomponer los cuerpos de
longitud 3 o superior en una cascada de producciones, teniendo cada una de
ellas un cuerpo formado sólo por dos variables.
La construcción para (a) es la
siguiente: para todo símbolo a que aparezca en un cuerpo de longitud 2 o
superior, creamos una nueva variable, por ejemplo A. Esta variable sólo
tiene una producción, A →a. Ahora empleamos A en lugar
de a en cualquier lugar que aparezca esta última dentro de un cuerpo de longitud
2 o superior. En este punto, toda producción tendrá un cuerpo formado por un
sólo símbolo terminal o por al menos dos variables y ningún símbolo terminal.
Para el paso (b), tenemos que
descomponer dichas producciones A→B1B2 · · ·Bk,
para k ≥ 3,
en un grupo de producciones con dos variables en cada cuerpo. Introducimos k−2 nuevas variables, C1, C2,
. . ., Ck−2.
La producción original se reemplaza por las k−1 producciones:
A→B1C1, C1 →B2C2. . . ,Ck−3 →Bk−2Ck−2, Ck−2 →Bk−1Bk
III.-
AUTÓMATA CON TRANSICIONES DE CERRADURA
Autómata
finito no determinista con transiciones ε (AFND-ε)
Además de
ser capaz de alcanzar más estados leyendo un símbolo, permite alcanzarlos sin
leer ningún símbolo. Si un estado tiene transiciones etiquetadas con 
, entonces el AFND
puede encontrarse en
cualquier de los estados alcanzables por las transiciones , directamente o a
través de otros estados con transiciones . El conjunto de
estados que pueden ser alcanzados mediante este método desde un estado q, se
denomina la clausura de q.
, entonces el AFND
puede encontrarse en
cualquier de los estados alcanzables por las transiciones , directamente o a
través de otros estados con transiciones . El conjunto de
estados que pueden ser alcanzados mediante este método desde un estado q, se
denomina la clausura de q.
Sin
embargo, puede observarse que todos estos tipos de autómatas pueden aceptar los mismos lenguajes.
Siempre se puede construir un AFD que acepte el mismo lenguaje que el dado por
un AFND.
Autómata
Finito con Transiciones -ε
Sea ε
una etiqueta en arcos. •
No
hay ningún cambio extra: la aceptación de w todavía se da como la existencia de
la ruta desde un estado de inicio a un estado de aceptación con etiqueta w. •
Pero ε
puede aparecer en los arcos, y significa que hay una cadena vacía (i.e., no
tiene una contribución visible para w).
III.I.- EJEMPLO DE UN
AUTÓMATA FINITO CON TRANSICIÓN DE CERRADURA
•
001 es aceptado siguiendo la ruta q, s, r, q, r, s, con la etiqueta 0ε01ε
= 001.
•
Podemos diseñar un autómata que acepte cadenas de números que tengan un signo
al inicio opcional, seguida posiblemente de una cadena de decimales, seguida de
un punto decimal y posiblemente de otra cadena de decimales.[3]
[4]IV.- AUTÓMATAS A
PILA
Existe un tipo de autómata que
define los lenguajes independientes del contexto. Dicho autómata, conocido como
“autómata a pila”, es una extensión
del autómata finito no determinista con transiciones-ε, el cual constituye una
forma de definir los lenguajes regulares. El autómata a pila es
fundamentalmente un AFN-ε con la adición de una pila. La pila se puede leer, se
pueden introducir elementos en ella y extraer sólo el elemento que está en la
parte superior de la misma, exactamente igual que la estructura de datos de una
“pila”.
Fundamentalmente, el autómata a
pila es un autómata finito no determinista con transiciones-ε y una capacidad adicional:
una pila en la que se puede almacenar una cadena de “símbolos de pila”. La
presencia de una pila significa que, a diferencia del autómata finito, el
autómata a pila puede “recordar” una cantidad infinita de información. Sin
embargo, a diferencia de las computadoras de propósito general, que también
tienen la capacidad de recordar una cantidad arbitrariamente grande de
información, el autómata a pila sólo puede acceder a la información disponible
en su pila de acuerdo con la forma de manipular una pila FIFO (first-in-first-out
way, primero en entrar primero en salir).
Así, existen lenguajes que podrían
ser reconocidos por determinados programas informáticos, pero no por cualquier
autómata a pila. De hecho, los autómatas a pila reconocen todos los lenguajes
independientes del contexto y sólo estos. Aunque existen muchos lenguajes que son
independientes del contexto, incluyendo algunos que hemos visto que no son
lenguajes regulares, también existen otros lenguajes simples de describir que
no son independientes del contexto. Un ejemplo de lenguaje no independiente del
contexto es {0n1n2n
| n ≥ 1}, el conjunto de cadenas formadas
por grupos iguales de ceros, unos y doses.
Un “control de estados finito” lee
las entradas, un símbolo cada vez. El autómata a pila puede observar el símbolo
colocado en la parte superior de la pila y llevar a cabo su transición
basándose en el estado actual, el símbolo de entrada y el símbolo que hay en la
parte superior de la pila. Alternativamente, puede hacer una transición
“espontánea”, utilizando ε como entrada
en lugar de un símbolo de entrada. En una transición, el autómata a pila:
1. Consume de la entrada el símbolo
que usa en la transición. Si como entrada se utiliza ε, entonces no se consume
ningún símbolo de entrada.
2. Pasa a un nuevo estado, que puede
o no ser el mismo que el estado anterior.
3. Reemplaza el símbolo de la parte
superior de la pila por cualquier cadena. La cadena puede ser ε, lo que
corresponde a una extracción de la pila. Podría ser el mismo símbolo que estaba
anteriormente en la cima de la pila; es decir, no se realiza ningún cambio en
la pila. También podría reemplazar el símbolo de la cima de la pila por otro
símbolo, lo que cambiaría la cima de la pila pero no añade ni extrae ningún símbolo.
Por último, el símbolo de la cima de la pila podría ser reemplazado por dos o
más símbolos, lo que (posiblemente) tendría el efecto de cambiar el símbolo de
la cima de la pila, añadiendo después uno o más nuevos símbolos a la pila.
IV. I.- DEFINICIÓN DE
AUTÓMATA A PILA
La notación formal de un autómata a pila incluye siete
componentes. Escribimos la especificación de un autómata a pila P de la forma siguiente:
P = (Q, Σ, Γ, δ, q0, Z0, F)
El significado de cada uno de los
componentes es el siguiente:
Q: Un conjunto finito de estados, como los estados de un
autómata finito.
Σ: Un conjunto finito de símbolos de entrada, también análogo
al componente correspondiente de un autómata finito.
[5]Γ: Un alfabeto de pila finito. Este componente, que no tiene análogo
en los autómatas finitos, es el conjunto de símbolos que pueden introducirse en
la pila.
δ: La función de transición. Como en el autómata finito, δ controla el
comportamiento del autómata. Formalmente,
δ toma como argumento δ (q, a, X), donde:
1. q es un estado de Q.
2. a es cualquier símbolo de entrada de Σ o a=ε, la cadena vacía, que se supone que no es un símbolo de
entrada.
3. X es un símbolo de la pila, es decir, pertenece a Γ.
La salida de δ es un conjunto
finito de pares (p, γ), donde p es el nuevo estado y γ es la cadena
de símbolos de la pila que reemplaza X
en la parte superior de la pila. Por ejemplo, si γ = ε, entonces se
extrae un elemento de la pila, si γ = X,
entonces la pila no cambia y si γ =YZ,
entonces X se reemplaza por Z e Y se introduce en la pila.
q0: El estado inicial. El autómata a pila se encuentra en este estado
antes de realizar ninguna transición.
Z0: El símbolo inicial. Inicialmente, la pila del autómata a pila
consta de una instancia de este símbolo y de nada más.
F: El conjunto de estados de aceptación o estados finales.
IV.II.- NOTACIÓN GRÁFICA
PARA LOS AUTÓMATAS A PILA
En ocasiones, un diagrama, que generaliza
el diagrama de transiciones de un autómata finito, mostrará más claramente
aspectos del comportamiento de un determinado autómata a pila. Por tanto, vamos
a ver y a utilizar un diagrama de
transiciones de un autómata a pila en el que:
a) Los nodos se corresponden con
los estados del autómata a pila.
b) Una flecha etiquetada como Inicio indica el estado inicial y los
estados con un círculo doble se corresponden con los estados de aceptación, al
igual que en los autómatas finitos.
c) Los arcos corresponden a las
transiciones del autómata a pila de la forma siguiente: un arco etiquetado con a, X/α del estado q al estado p quiere decir que δ (q,
a, X) contiene el par (p, α),
quizá entre otros pares. Es decir, la etiqueta del arco nos indica qué entrada
se utiliza y también proporciona los elementos situados en la cima de la pila
nuevo y antiguo.
Lo único que el diagrama no
proporciona es el símbolo inicial. Por convenio, es Z0, a menos que se indique otra cosa.
IV.III.- REPRESENTACION DE
AUTOMATA DE PILA
Por tanto, representaremos la
configuración de un autómata a pila mediante (q, w, γ), donde
1. q es el estado,
2. w es lo que queda de la entrada y
3. γ es el contenido de la pila.
Por convenio, especificamos la
parte superior de la pila en el extremo izquierdo deγ y la parte inferior en el
extremo derecho. Este triplete se denomina descripción instantánea o ID (instantaneous description, o configuración del autómata a pila).
IV.IV.- DEFINICIÓN DE AUTÓMATA A PILA DETERMINISTA
Intuitivamente, un autómata a pila
es determinista si en ninguna situación existe la posibilidad de elegir entre dos
o más movimientos. Estas posibilidades son de dos tipos. Si δ (q,a,X) contiene más de un par,
entonces sin duda el autómata a pila es no determinista porque podemos elegir
entre estos pares a la hora de decidir el siguiente movimiento. Sin embargo,
incluso aunque δ (q,a,X) tenga
siempre un solo elemento, tendríamos todavía la posibilidad de elegir entre
emplear un símbolo de entrada real o realizar un movimiento sobre ε.
Por tanto, decimos que un autómata
a pila P = (Q, Σ, Γ,δ ,q0,Z0,F) es determinista (y lo denominamos APD, autómata
a pila determinista) si y sólo si se cumplen las siguientes condiciones:
1. δ (q,a,X) tiene como máximo un elemento para cualquier q de Q, a de Σ o a =ε, y X de Γ.
2. Si δ (q,a,X) no está vacío para algún a de Σ, entonces δ (q,ε,X) tiene que estar vacío.
La estrategia del APD es almacenar
ceros y unos en su pila hasta ver el marcador central c. Pasar entonces a otro estado, en el que los símbolos de
entrada se emparejan con los símbolos de la pila y extraerlos de la pila si se
corresponden. Si se detecta alguna no correspondencia, muere: su entrada no
puede ser de la forma wcwR. Si consigue
extraer de la pila hasta el símbolo inicial, el cual marca el fondo de la pila,
entonces acepta la entrada.
REFERENCIAS BIBLIOGRÁFICAS
Ø “Generativismo”
(2008) [en línea], disponible en
http://www.babylon.com/definition/generativismo/Spanish, recuperado 5 de
septiembre de 2008
Ø
“Chomsky”
(2008) [en línea], disponible en http://es.wikipedia.org/wiki/Chomsky,
recuperado septiembre 20.
Niño
Rojas, V.M. (2007), Semiótica y Lingüística, Bogotá, ed. Ecoes
Zabala,
V (1982), Funcionalismo estructural, Madrid, ed. Alianza.
Ø Introducción
a la teoría de autómatas, lenguajes y computación.
Hopcroft, J. E.; Motwani, R.; Ullman, J. D.
Ed.
PEARSON EDUCACIÓN S.A., Madrid, 2007.
No hay comentarios:
Publicar un comentario