Respuestas a las preguntas de teoría de los exámenes de TALF

Ahora que se acabaron las practicas y las hojas de talf lo único que queda son las respuestas a las preguntas de teoría y como no las tengo  podíamos intentar completarlas entre todos (dejáis un comentario con la pregunta y la respuesta).

Ya están acabadas, gracias por vuestra nula colaboración

Exámen Xuño de 2005

Dado dos lenguajes regulares L1 y L2 . ¿El lenguaje de unión L1 ∪ L2 también es un lenguaje regular?

Cierto, porque L1 y L2 al ser regulares existe una expresión regular que los define cada lenguaje, dichas expresiones se pueden concatenar para generar el lenguaje que define la union.

¿Un autómata finito determinista siembre tiene un número mayor de estados que un autómata finito no–determinista asumiendo que ambos aceptan el mismo lenguaje?

Falso, sobre un autómata  finito determinista podemos añadir transiciones epsilon a nuevos estados sin alterar el lenguaje que genera

¿L+ != L∗ si y solo si ∈ L?

Respuesta

¿Existen lenguajes libres de contexto que no son regulares?

Verdadero Un lenguaje libre de contexto es generado por una gramática libre de contexto y la gramática $ -> a$b | € genera el lenguaje no regular a^nb^n : N>=0

¿Si una gramática es ambigua también el lenguaje que genera es ambiguo?

No, para que un lenguaje sea ambiguo todas las gramáticas que lo generan tienen que ser ambiguas no es suficiente con una

¿Una gramática regular puede ser ambigua?

Si, por ejemplo
$ -> aA | aB
A->b
B->b (es regular y ambigua)

¿Existen expresiones regulares que definen lenguajes que no se pueden aceptar con un autómata finito con pila?

No porque para toda ER existe un AF y por definición todo AF es un AFP en el que la pila no se mueve

¿Un autómata finito con pila determinista puede realizar cambios de estados sin leer un símbolo de la entrada?

Si, siempre cuando realice una lectura Epsilón y para esa lectura solo exista un camino

¿Si dos expresiones regulares no son iguales, los lenguajes que definen pueden ser iguales?

Si,    expresiones regulares distintas que generan el mismo lenguaje

¿Para L = L(α) con α = a∗ b∗ c∗ , RL tiene índice 4?

Si, el autómata mínimo completo tiene 4 estadosAutómata mínimo completa a*b*c*

Exámen Setembro de 2005

Dado dos lenguajes regulares L1 y L2 . ¿El lenguaje de intersección L1 ∩ L2 también es un lenguaje regular?
Por las lyes de De Morgan sabemos que De Morgan

Complemento de Lenguaje regularque es un Lenguaje regular, porque el complemento de un lenguaje regular es un lenguaje regular

Complemento de Lenguaje Regularque es un Lenguaje regular, porque el complemento de un lenguaje regular es un lenguaje regular

Unión de lenguaje regular que es un lenguaje regular, porque la unión de dos lenguajes regulares genera un lenguaje regular

Complemento de Lenguaje regular que es un Lenguaje regular, porque el complemento de un lenguaje regular es un lenguaje regular

¿Un autómata finito no–determinista siempre tiene un número menor de estados que un autómata finito determinista asumiendo que ambos aceptan el mismo lenguaje?
No,

AFDAFND

¿L+ = L∗ si y solo si ∈ L?

Respuesta

¿Existen lenguajes libres de contexto deterministas que no son regulares?

Verdadero Un lenguaje libre de contexto es generado por una gramática libre de contexto y la gramática $ -> a$b | € genera el lenguaje no regular a^nb^n : N>=0

¿Si un lenguaje es ambiguo todas las gramáticas que generan el lenguaje son ambiguas?

Sí, un lenguaje es ambiguo si todas las gramáticas que generan el lenguaje son ambiguas.

¿Una gramática regular puede ser ambigua?

Si, por ejemplo
$ -> aA | aB
A->b
B->b (es regular y ambigua)

 

¿Existen expresiones regulares que definen lenguajes que no se pueden aceptar con un autómata finito determinista?
No, porque toda expresión regular se puede transformar en un AFND-Epsilón y este en un AFD

¿Un autómata finito con pila determinista puede realizar cambios de estados sin cambiar el contenido de la pila?

Si, siempre cuando realice una lectura Epsilón y para esa lectura solo exista un camino

¿Expresiones regulares definen lenguajes que se pueden aceptar con un autómata finito con pila?

Si, para toda ER existe un AF y por definición todo AF es un AFP en el que la pila no se mueve

¿Para L = L(α) con α = a∗ b∗ , RL tiene índice 4?

Respuesta

Exámen Decembro de 2005

Dado un lenguaje regular L sobre el alfabeto Σ. ¿El lenguaje complementario de L, es decir, Σ∗ − L, también es un lenguaje regular?

L = L1 = Σ*−L1 es regular, porque podemos construir, dado un AFD completo M1 que acepta L1, un AFD M que acepta L simplemente ‘invirtiendo’ sus estados finales, es decir, los estados no finales de M1 serán los estados finales de M y los finales se convierten en los no finales.

¿Existen autómatas finitos no–deterministas que tengan menos estados que sus equivalentes autómatas deterministas mínimos y completos que acepten los mismos lenguajes?
Respuesta

¿La palabra vacia pertenece a cualquier lenguaje formal?

No, porque Epsilón tiene que pertenecer al subconjunto de las palabras

¿Existen lenguajes libres de contexto deterministas que no sean regulares?

Verdadero Un lenguaje libre de contexto es generado por una gramática libre de contexto y la gramática $ -> a$b | € genera el lenguaje no regular a^nb^n : N>=0

¿Una gramática libre de contexto puede ser ambigua?

Si,

Gramática libre de contexto ambigua

¿Un lenguaje libre de contexto puede ser ambiguo?

Sí, solo podemos afirmar que no son ambiguos los lenguajes regulares. Para que sea ambiguo todas las gramaticas que lo generan deben ser ambiguas

¿Si dos expresiones regulares son diferentes, entonces obviamente definen lenguajes regulares diferentes?
No, dos expresiones regulares pueden definir el mismo lenguaje    expresiones regulares distintas que generan el mismo lenguaje

¿Si un lenguaje es finito, entonces es regular?

Si porque podemos construir un AF que lo genere con un camino para cada palabra que genere ese lenguaje , entonces el lenguaje es regular.

¿Un autómata finito con pila determinista puede realizar cambios de estados sin cambiar el contenido de la pila?

Si, siempre cuando realice una lectura Epsilón y para esa lectura solo exista un camino

¿Se puede averiguar si cualquier dos gramáticas de tipo 3 que tienen sistemas de producciones diferentes generan el mismo lenguaje regular?

Sí, obteniendo los AFD-min de ambas gramaticas y comprobando si son iguales generan el mismo lenguaje.

Exámen Xuño de 2006

Dado cualquier gramática G. ¿Se puede hallar siempre una gramática G ambigua que genera el mismo lenguage que G?

Si, porque en toda gramática no ambigua se pueden introducir producciones redundantes para generar una gramática ambigua equivalente

¿Existe una expresión regular que define un lenguaje que se puede aceptar con un autómata finito con pila?

Sí, si tenemos una ER tenemos un AF y por definición un AF es un AFP en el que la pila no se mueve.

Sea ε ∈ L y M un AFND–ε con L(M ) = L. ¿Entonces el estado inicial de M necesariamente es un estado final?

No porque al ser un AFND–ε se puede pasar de un estado a otro sin consumir nada (consumiendo solo ε ) Si fuese AFD o AFND la respuesta seria Si .

autómata respuesta

¿El AFD mínimo que acepta L tiene tantos estados finales que hay clases de equivalencia de RL que cubren L, (es decir, si unimos las palabras de dichas clases, obtenemos justamente L)?

Respuesta

¿Si Indice(RL ) = ∞, entonces L no es libre de contexto?

Respuesta

Exámen Setembro de 2006

¿Existe un lenguaje regular ambiguo?

Todo lenguaje regular puede ser definido por un AFD-mínimo y un AFD-mínimo se puede transformar en una gramática lineal no ambigua

Sean x, y, y w palabras sobre algún alfabeto. Si x es prefijo de w, e y es sufijo de w y x = y, entonces x = y = w, ¿es verdad?

falso,

demostracion

Si todos los n > 1 estados de un AFD (autómata finito determinista) completo son estados finales, entonces el AFD no es mínimo.

Si porque al aplicar el algoritmo de minimización todas las casillas quedarian sin marcar por lo que todos los estados serian equivalentes.

Nota : Si en el enunciado no apareciese completo seria Falso.

¿La concatenación de dos lenguajes libres de contexto produce de nuevo un lenguaje libre de contexto?

Respuesta

¿Se puede averiguar si una gramática libre de contexto G genera alguna palabra, es decir, averiguar si L(G) = ∅?

Si comprobando que $ es generativo.

Exámen Decembro de 2006

¿Existe un lenguaje libre de contexto ambiguo?

Respuesta

Sean x, y, y w palabras sobre algún alfabeto. Si x es prefijo de w, e y es sufijo de w y x = y, entonces x = y = w, ¿es verdad?
Respuesta

Si todos los estados de un AFD (autómata finito determinista) completo M son estados finales, entonces el Indice(RL(M ) ) = 1?

Sí, porque en el algoritmo de minimización todas las casillas quedarían sin marcar , siendo todos equivalentes , quedando un solo estado.

¿La intersección de dos lenguajes regulares produce de nuevo un lenguaje regular?

Por las lyes de De Morgan sabemos que De Morgan

Complemento de Lenguaje regularque es un Lenguaje regular, porque el complemento de un lenguaje regular es un lenguaje regular

Complemento de Lenguaje Regularque es un Lenguaje regular, porque el complemento de un lenguaje regular es un lenguaje regular

Unión de lenguaje regular que es un lenguaje regular, porque la unión de dos lenguajes regulares genera un lenguaje regular

Complemento de Lenguaje regular que es un Lenguaje regular, porque el complemento de un lenguaje regular es un lenguaje regular

¿Se puede averiguar si una gramática libre de contexto G genera la palabra vacía, es decir, averiguar si ε ∈ L(G)?

Respuesta

Exámen Xuño de 2007

Si existe una gramática lineal por la izquierda G que genera un lenguaje formal L, entonces L es finito. ¿Es correcto?
No

S -> aB
B -> aB | a

Si una expresión regular no contiene ningún asterisco (de Kleene), entonces el lenguaje es finito. ¿Es correcto?

No, puede contener el operador ⁺

Si un autómata finito determinista mínimo tiene dos estados finales, entonces adicionalmente tiene también por lo menos un estado no final. ¿Es correcto?

Si, porque si son todos estados finales el autómata mínimo estaría compuesto por un único estado final

¿Un autómata finito con pila (no–determinista) que nunca vacía su pila puede aceptar alguna palabra?

Si, por estado final

¿Dada una gramática lineal por la derecha ambigua G, es posible construir una grámatica lineal por la izquierda no–ambigua G que genera el mismo lenguaje, es decir, con L(G ) = L(G)?

Una gramática lineal genera un lenguaje regular  y sobre un lenguaje regular se puede generar un autómata y sobre este obtener una gramática lineal por la izquierda no ambigua

Exámen Setembro de 2007

Sean $ −→∗ w y $ −→∗ w dos derivaciones distintas para una palabra w ∈ L ⊂ {a, b, c}∗ y una gramática G con L(G) = L. ¿El lenguage L entonces es ambiguo?

Respuesta

¿Si la unión y el complemento son operaciones cerradas para un tipo de lenguajes formales, entonces la intersección también es una operación cerrada para este tipo?

Respuesta

Para cualquier lenguaje regular L existe un AFND– M con L(M ) = L que contiene un solo estado final. ¿Es correcto?

Si, porque sobre el AFD podemos crear un nuevo estado final incluir transiciones Epsilóndesde el resto de estados finales y transformar los otros estados finales en no finales

Si un autómata finito determinista mínimo tiene dos estados finales, entonces adicionalmente tiene también por lo menos un estado no final. ¿Es correcto?

Respuesta

Una gramática en Forma Normal de Chomsky nunca puede ser ambigua. ¿Es correcto?

Respuesta

Examen Junio de 2008

Sea L un lenguaje regular y , es decir, L1 contiene un subconjunto de las palabras de L. ¿El lenguaje L1 entonces es necesariamente regular?

No, es regular y L1 puede ser libre de contexto

Si dos autómatas finitos deterministas son equivalentes, entonces tienen el mismo numero de estados finales. ¿es correcto?

No.

Si un autómata finito determinista mínimo tiene cuatro estados , por lo menos uno de ellos es un estado no final. ¿Es correcto?

Si, porque si fueran todos finales en la minimización quedaría un único estado final equivalente

Una gramática en Forma Normal de Chomsky puede ser ambigua. ¿Es correcto?

Si, ejemplo:

Examen Diciembre de 2008

¿Existe un lenguaje regular ambiguo?

Un lenguaje ambiguo es aquel que todas las gramáticas que lo generan son ambiguas, pero para todo lenguaje regular se puede crear un AFD mínimo de que obtenemos una gramática no ambigua

Sean x,y, y w palabras sobre algún alfabeto. Si x e y son prefijos de w, entonces x es prefijo y, ¿es verdad?

No,

y=a

x=ab

w=abc

Si todos los estados de un AFD (autómata finito determinista) completo M son estados finales, entonces el Indice(RL(M)) =1?

Si porque al aplicar el algoritmo de minimización quedaría un único estado final equivalente

¿La unión de dos lenguajes libres de contexto produce de nuevo un lenguaje libre de contexto?

Si partimos de las gramáticas que generan los lenguajes dos lenguajes libres de contexto L1 y L2 podemos crear una nueva gramática donde su símbolo inicial enlace los dos lenguajes $ -> $L1 | $L2

¿Se puede averiguar si una gramática libre de contexto G genera alguna palabra, es decir, averiguar si ?

Si, comprobando que el símbolo inicial es generativo.

Examen Junio de 2009

Sea L un lenguaje regular. ¿Existe una gramática lineal por la derecha G que genera L, es decir, L(G)=L, y cuyo numero de variables es igual a Indice(RL)?

Si. Un lenguaje regular es aceptado por un AFD mínimo, con un numero de estados igual al Indice(RL). Al convertir el AFD mínimo en una gramática lineal por la derecha, cada estado sera una variable.

Si una expresión regular contiene un asterisco (de Kleene), entonces el lenguaje es infinito. ¿Es correcto?

No.

Si un autómata finito determinista mínimo (completo) tiene un solo estado no final (a parte de sus estados finales), entonces dicho estado no final (si lo dibujamos) tiene una arista reflexiva. ¿Es correcto?

No. Ejemplo:

¿Para cada autómata finito con pila no determinista (AFPND) que acepta con estado final existe una AFPND que acepta con pila vacía?

Si , porque un AFPND que acepta con pila vacía se puede transformar en AFPND que acepta en estado final y viceversa usando el método de la simulación.

¿Dada una gramática lineal por la derecha ambigua G, es posible construir una gramática lineal por la derecha no ambigua G’ que genera el mismo lenguaje, es decir, con L(G’)=L(G)?

Si. Una gramática lineal por la derecha genera un lenguaje regular y un lenguaje regular se puede modelar con un AFD mínimo , este AFD mínimo puede ser convertido en una gramática lineal por la derecha no ambigua.

Examen Septiembre de 2009

Sea L un lenguaje regular. ¿Existe una gramática lineal por la derecha G que genera L, es decir, L(G)=L, y cuyo numero de variables es igual a Indice(RL)+5?

Si. Un lenguaje regular es aceptado por un AFD mínimo, con un numero de estados igual al Indice(RL). Al convertir el AFD mínimo en una gramática lineal por la derecha, cada estado sera una variable. Sobre esta gramática, podemos añadir el numero de variables redundantes que queramos, en este caso 5.

Si una expresión regular contiene un asterisco (de Kleene), entonces el lenguaje es infinito. ¿Es correcto?

No.

Si un autómata finito determinista mínimo (completo) tiene un solo estado no final (a parte de sus estados finales), entonces dicho estado no final (si lo dibujamos) tiene una arista reflexiva. ¿Es correcto?

No. Ejemplo:

¿Para cada autómata finito con pila no determinista (AFPND) que acepta con pila vacía existe una AFPND que acepta en estado final?

Si , porque un AFPND que acepta con pila vacía se puede transformar en AFPND que acepta en estado final y viceversa usando el método de la simulación.

¿Dada una gramática lineal por la izquierda ambigua G, es posible construir una gramática lineal por la derecha no ambigua G’ que genera el mismo lenguaje, es decir, con L(G’)=L(G)?

Si. Una gramática lineal por la izquierda genera un lenguaje regular y un lenguaje regular se puede modelar con un AFD mínimo , este AFD mínimo puede ser convertido en una gramática lineal por la derecha no ambigua.

Examen Diciembre de 2009

Sea L un lenguaje regular ¿Existe una gramática lineal por la derecha G que genera ?

Si, Si L es regular podemos crear un AFD que acepta el lenguaje, sobre ese AFD aplicando el método del complemento obtenemos un AFD que acepta y a partir de este ultimo AFD podemos crear una gramática linear por la derecha que genera 

Si una expresión regular contiene el un asterisco (de Kleene), entonces el lenguaje es infinito. ¿Es correcto?

No.

¿Que se entiende bajo el concepto que una operación entre lenguajes sea una operación cerrada?

Los lenguajes son un tipo de conjuntos. Que una operación sea cerrada quiere decir que cuando esta operación se aplica a elementos de ese conjunto, en este caso a un lenguaje, el resultado sigue estando en ese conjunto, es decir, sigue siendo un lenguaje. Ejemplo: A union Bes un lenguaje regular si A,B son lenguajes regulares.

Sea L un lenguaje libre de contexto. ¿Existe un lenguaje L’ tal que L union L'sea regular?

Si, es regular y si L es libre de contexto por lo tanto para todo lenguaje L libre de contexto la unión con su complemento genera un lenguaje regular

¿Dada una gramática lineal por la izquierda ambigua G, es posible construir una gramática lineal por la derecha no ambigua G’ que genera el mismo lenguaje, es decir, con L(G’)=L(G)?

Si. Una gramática lineal por la izquierda genera un lenguaje regular y un lenguaje regular se puede modelar con un AFD mínimo , este AFD mínimo puede ser convertido en una gramática lineal por la derecha no ambigua.

Segundo Examen Practico TALF Modelo 3

Este esta incompleto si algun alma caritativa copio el primer ejercicio lo puede poner en los comentarios.

Ejercicio 2: Describe el lenguaje que genera la siguiente gramática.

Gramática enunciado Respuesta genera palindromos

Ejercicio 3: Crea una gramática que genere números  hexadecimales  e  indicar el arbol de derivación para 5b3

La gramática que genera números hexadecimales es la siguiente:

Gramática hexadecimalabrimos el JFlap y pinchamos en la opción “Grammar”

nueva Gramática JFlap

modelamos la gramática

Gramática Hexadecimal modeladapara generar el árbol de derivación utilizamos la opción “Brute Force Parse” en el menú “Input” que nos abrirá  una nueva pestaña

Input grammar JFlap

introducimos 5b3 en la caja de texto y pinchamos en “Start”  esperamos que acepte la palabra para luego presionar en el botón “step” hasta obtener el árbol de derivación completo que es el siguiente

Árbol derivación 5b3

Segundo Examen Practico TALF Modelo 2

1. Comprobar si son equivalentes:

a)

  • S -> aaS
  • S -> bB
  • B -> bB
  • B -> b

b)

Autómata comprobar equivalencia examen

c)

Expresión Regular

para compara si los anteriores elementos debemos transformar la expresión regular y la gramática  en una expresión regular

para la expresión  regular  los pasos son los siguientes :

Abrimos el JFlap y seleccionamos la Opción “Regular Expression

Expresion Regular JFlap

insertamos la expresión regular en el JFlap λ

Expresión regular insertada

Ahora la convertimos en un autómata  con la opción “Convert NFA” del menú “convert

Convirtiendo expresión regular en autómata finito no determinista

pinchamos en “Do All” y “Export”  lo que nos mostrara una nueva ventana con el autómata equivalente  a la expresión regular

Autómata Equivalente expresión regularguardamos el autómata generado para compararlo después .

Seguidamente modelamos la gramática en JFlap para ello abrimos el JFlap y seleccionamos la opción “Grammar

nueva Gramática JFlapmodelamos la gramática en la nueva ventana

Gramática modeladacomo es una gramática lineal por la derecha seleccionamos la opción “Convert Right Lineal Grammar to FA” en el menú “Convert

Convertir Gramática Lineal por la derecha a autómata finitopinchamos en “Show All” y  “Export” lo que nos creara un autómata equivalente a la gramática

Autómata Equivalente Gramáticaahora con los tres autómatas abiertos  vamos a comparar equivalencias

Tres automatas abiertos

Para comparar la equivalencia entre autómatas seleccionamos la opción  “Compare Equivalence” en el menú “Test”  lo que nos preguntara con que autómata queremos comparar

El resultado es: La gramática y  la expresión regular son equivalentes

2. Dada a seguinte gramática

  • A -> CB2
  • A -> 1B
  • A -> ε
  • B -> BC
  • B ->1
  • C -> 2

a) Transformar a forma normal de Chomsky

modelamos la gramática en JFLAP

Gramática a normalizarPara convertirla a Chomsky seleccionamos la opción “Transform Grammar” en el menú “Convert“, nos advierte que eliminara el símbolo Lambda

Eliminación símbolo vacíopinchamos en “Do All” y “Procceed” y se creara  una nueva pestaña

Conversión Chomsky JFlapPinchamos en “Do All” y “Export” y aparecerá la gramática convertida a forma normal de Chomsky

Gramática convertida a Chomsky

b) Convertir a resultante a un autómata de pila polo método LL

Sobre la gramática generada pinchamos en la opción  “Convert CFG to PDA (LL)” en el menú “Convert” nos abrirá una nueva pestaña

Convert to PDA LL

pinchamos en “Show All” y “Export” lo que nos mostrara el autómata de pila

Autómata de pilac) Obten a traza para a cadea de entrada 1122

Menú “Input” opción “Step by State”  abre un dialogo insertamos la cadena 1122 y seleccionamos Final State

Trazale damos a step hasta que aparezca un estado en verde lo seleccionamos y pinchamos en trace la traza final es la siguiente:

Traza Completa

Segundo Examen Practico TALF Modelo 1

Modelo 1

Dada a expresión regular (a+b)*cc(b+a)*
Debuxa o autómata mínimo determinista completo equivalente

Abrimos el JFlap y seleccionamos la opción “Regular Expression”

Regular Expression JFlap

nos aparece una ventana para introducir la expresión regular, la introducimos

expresión regular Introducida

primeramente tendremos que transformarla en un autómata seleccionamos la opción “Convert to NFA” en el menú “Convert” nos abrirá una ventana para iniciar la conversión.

Regexp to NFA JFlapPinchamos en el botón “Do All”  y en “Export”  con lo que obtendremos un autómata que acepta las mismas palabras que la expresión regular.

Expresión regular transformada en un autómata

este autómata no es mínimo por lo tanto debemos minimizarlo para eso debemos transformarlo en un autómata determinista, para ello seleccionamos la opción “convert to DFA” en el menú “Convert

Convirtiendo de No determinista en determinista

Pinchamos en el botón “Complete” y luego en “Done” con lo que aparecerá una nueva ventana con el autómata determinista

Autómata determinista convertidoEste autómata determinista puede no ser mínimo así que lo necesitamos minimizar, para ello seleccionamos la opción “Minimize DFA” en el menú “Convert”  lo que nos abrirá una nueva pestaña para realizar la conversión

DFA Minimizacion JFlapSeleccionamos el nodo raíz del árbol “El que no tiene ningún nodo superior” y pinchamos en “Complete Subtree” para luego pinchar en “Finish” con lo que creara una nueva ventana para la minimización

minimizacion AFDpinchamos en “Complete” y en “Done” lo que nos creara una nueva ventana con el autómata mínimo

Autómata mínimo

pero este autómata no es completo para eso introduciremos un estado de error al que dirigiremos todas las transiciones que no pertenezcan al autómata.

Autómata mínimo completo

Indica si dita expresión regular e equivalente a seguinte gramática, e o proceso seguido para averigualo.

  • S-    ->    B
  • A    ->    ε
  • B    ->    C
  • C    ->    B
  • I    ->    A
  • C    ->    D
  • E    ->    F
  • I    ->    H
  • H    ->    J
  • K    ->    I
  • J    ->    L
  • O    ->    K
  • M    ->    K
  • Q    ->    C
  • D    ->    cE
  • H    ->    I
  • P    ->    R
  • R    ->    aT
  • N    ->    aO
  • P    ->    U
  • L    ->    bM
  • J    ->    N
  • V    ->    Q
  • F    ->    cG
  • B    ->    P
  • G    ->    H
  • T    ->    Q
  • U    ->    bV

Abrimos el JFlap y creamos una gramática nueva

Creando gramática JFlapinsertamos la gramática

Gramática Insertadauna vez insertada la gramática necesitamos convertirla en un autómata para  verificar si es equivalente al autómata mínimo del apartado anterior para ello seleccionamos la opción “Convert Right-Lineal Grammar to FA” en el menú “Convert” nos abrirá la siguiente ventana.

Convirtiendo Grammar to FApinchamos en “Show All” para seleccionar todas las producciones, y en “Export” lo que nos creara una ventana con un Autómata equivalente a la gramática

Autómata equivalenteAhora es el momento de comprobar la equivalencia entre autómatas para ello abrimos el autómata mínimo completo del apartado anterior y en la ventana de cualquiera de los dos autómatas seleccionamos la opción  “Compare Equivalence” en el menú test nos abrirá una ventana preguntado que autómata queremos comparar y nos mostrara que SON EQUIVALENTES

Equivalentes

2 Dada a gramatica
S-> S mais S | S cuadrado | S cubo | raiz S | X
X-> XX | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Indica si acepta as seguintes expresións, e en caso afirmativo, obter o árbore de derivación proporcionado polo JFlap

Abrimos JFlap y seleccionamos la opción Grammar

Creando gramática JFlappara modelar la gramática deberemos cambiaremos las palabras mais por a, cuadrado por b, cubo por c y raiz por d. Modelamos la gramatica

Gramática ejercicio 2para obtener el árbol de derivación seleccionamos la opción “Brute Force Parse” en el menú “input” lo que nos abrirá la siguiente ventana

Brute force parse grammar JFlapintroducimos la palabra a probar  en la caja de texto input y pinchamos en  “Start”

luego pincharemos en step hasta que nos complete el árbol de derivación

  • 00 mais 15 cubo (00a15c)

árbol 00a15c

  • raiz 123 cuadrado (d123b)

arbol d123b

  • 7 mas raiz 3 (7ad3)

arbol 7ad3

Hoja 12 (18 de Mayo de 2010)

P1: Construye un autómata finito de pila no-determinista (AFPND) que acepta las mismas palabras que genera la gramática de la hoja 11, apartado 2.

Partimos de la siguiente gramática

gramática a transformar

para generar un Autómata de pila a partir de una gramática libre de contexto necesitamos crear un autómata de pila con tres estados.

El estado inicial q0 tiene una transición a q1 leyendo de la cima de la pila el símbolo de pila vaciá, e insertando en la pila el símbolo inicial de la gramática ($),todo esto sin consumir ningún símbolo de la palabra de entrada

en el estado q1 insertamos para cada producción de la gramática una transición consigo mismo en la que se consume el símbolo que genera la producción (parte izquierda $,A,B,I) y se inserta en la pila la derivación (parte derecha A,B,IaI,). Todas estas transiciones no consumen ningún símbolo de la palabra

Para los símbolos terminales se inserta una transición en el estado q1 que consume el un símbolo de la palabra siempre y cuando este símbolo este en el tope de la pila sacándolo de ella.

Finalmente se inserta una transición al estado q2 leyendo el indicador de pila vaciá y volviendo a insertar dicho símbolo, el autómata de pila quedaría definido de la siguiente forma:

Autómata de Pilaverificamos el autómata teniendo en cuenta de que acepta por pila vaciá.

Verificacion automata de pila

Fuente: www.cs.rpi.edu/~drinep/modcomp/class11-12.ppt

Practica 9: Autómatas de pila con JFLAP

El enunciado en este enlace Practica 9:Autómatas de pila

1. Dada la siguiente gramática libre de contexto

  • S → λ
  • S → xAy
  • A → λ
  • A → xAy
  • S → xByy
  • B → xByy
  • B → λ

a. Crea un autómata de pila que acepte el lenguaje generado por dicha gramática

Seleccionamos la opción grammar en JFlap e introducimos la gramática

Gramática introducida JFlapuna vez introducida la gramática seleccionamos el menú “Convert” y seleccionamos la opción “Convert CFG to PDA (LL)” nos mostrara una nueva pestaña para realizar la conversión

Convirtiendo gramática libre de contexto a autómata finito de pilaPinchamos en el botón “Show all” para seleccionar todas las producciones y seguidamente en “export” con lo que obtendremos nuestro autómata de pila.

Autómata de pila

b. Transfórmala a forma normal de Chomsky.

Sobre la gramática anterior seleccionamos la opción  “Transform Grammar” en el menú “Convert

nos mostrara un mensaje de que la nueva gramática no generara la palabra ε

Transform grammar lambda problemaceptamos el mensaje y aparecerá una nueva pestaña indicándonos las acciones a realizar para transformar la gramática.

paso 1 seleccionar símbolos que generen ε  para eliminarlos

Eliminacion lambda JFlapPaso 2. Conversión a Chomsky

Chomsky converter JFlap

Al pinchar en el botón “export”  obtendremos nuestra gramática en forma normal de Chomsky.

Gramática Chomsky

c. Comprueba la equivalencia de los autómatas al menos con las siguientes palabras, e indica la traza en cada caso

para obtener las trazas para palabras que deseamos probar seleccionamos la opción “Step by State” en el menú “input

xyyy

para el AFP generado a partir de la gramática libre de contexto :

Rechaza la palabra.

para el AFP generado a partir de la gramática en forma normal de Chomsky:

Rechaza la palabra.

xy

para el AFP generado a partir de la gramática libre de contexto :

Traza xy AFP gramática

para el AFP generado a partir de la gramática en forma normal de Chomsky:

Traza XY gramática Forma Normal Chomsky

xxxyyyyyy

para el AFP generado a partir de la gramática libre de contexto :

Traza xxxyyyyyy AFP generada de gramática

para el AFP generado a partir de la gramática en forma normal de Chomsky:

Gran Traza Chomsky

xyxy

para el AFP generado a partir de la gramática libre de contexto :

Rechaza la palabra

para el AFP generado a partir de la gramática en forma normal de Chomsky:

Rechaza la palabra

ε

para el AFP generado a partir de la gramática libre de contexto :

Traza epsilon gramática libre de contexto

para el AFP generado a partir de la gramática en forma normal de Chomsky:

Rechaza la palabra

d. Intenta describir que lenguaje genera

el lenguaje esta formado por la palabra vacio, o por un conjunto de caracteres x seguidos de un conjunto de caracteres y.

2. Prueba cadenas reconocidas por el siguiente autómata de pila

para insertar el autómata de pila en JFlap seleccionamos “Pusdown Automaton”

Autómata de pila JFlap

seleccionamos la opción “Single Character Input” y modelamos el autómata en JFlap

Autómata de pila pregunta 2

para obtener las trazas para palabras que deseamos probar seleccionamos la opción “Step by State” en el menú “input

aabb

Traza aabbopci

aabbbb

Traza aabbbb

abtraza ababb

Traza abb

Hoja 11 (11 de Mayo de 2010)

P1: Construye una gramática libre de contexto G que genera todas las palabras sobre el alfabeto {a, b} que tienen el mismo número de a’s y b’s, es decir,

L(G) = {ε, ab, ba, aabb, abab, baab, abba, baba, bbaa, aaabbb, aababb, . . .}

La gramática a generada es la siguiente:

Gramática libre de contexto pregunta 1

abrimos el JFlap y comprobamos si acepta las palabras del lenguaje

pregunta uno acepta palabrasgeneramos un archivo con diversas palabras con los caracteres a y b para verificar que no acepta las palabras que no cumplen la regla

Verificar Gramatica

P2: Construye una gramática libre de contexto G que genera todas las palabras sobre el alfabeto {a, b} que tienen un número diferente de a’s y b’s (ayuda: amplía la gramática del primer punto).

Para construir esta gramatica nos basaremos en las producciones anteriores  evitando la producción de la palabra vaciá y dividiendo el problema en dos  grupos palabras con mayor numero de letras a que de b (A) y palabras con mayor numero de letras b que de a (B). para ello simplemente evitaremos que las producciones terminales de A y B generen ε y permitan introducir un numero ilimitado de as y de bes.

Gramática libre de contexto pregunta 2

verificamos algunas palabras en el JFlap

JFlap Gramatica 2

Practica 8 Gramáticas libres de contexto en JFLAP

El enunciado aquí 8 Gramaticas libres de contexto

1.- Sigue con el JFLAP el proceso de conversión a Forma Normal de Chomsky de la siguiente gramática

  • S → sA
  • A → BC
  • B →ε
  • A →a
  • C →ε

Abrimos JFlap y pinchamos en el botón “Grammar” nos aparecerá una ventana para introducir la gramatica

introduciendo gramática JFLAP

Introducimos las producciones para la gramática

gramática introducida en JFLAP

Para convertir la gramática a la forma normal de Chomsky seleccionamos la opción Convert -> Transform Grammar

Conversion JFLAP a forma normal ChomskyEsta conversión esta compuesta de varios pasos:

Eliminación de Landa

Conversión JFLAP Chomsky paso 1 eliminación epsilon

Eliminación de unitarias A->B

Eliminación de produciones unitarias

Eliminación de producciones no usadas

Eliminación de producciones no usadasY finalmente tras ajustar las producciones la conversión a Chomsky

Transformación producciones ChomskyLo cual nos generara la gramatica de Chomsky

Gramática Convertida

2. La gramática S → x | y | z | S + S | S – S | S * S | S/S | (S) es libre de contexto y sirve para expresiones enteras algebraicas sintácticamente correctas sobre las variables x, y, z. Comprueba si son correctas las siguientes expresiones, y obtén su árbol de derivación.

modelamos la gramática en JFlap

Gramatica Ejercicio 2Para comprobar las expresiones y obtener su árbol de derivación seleccionamos la opción Input->Brute Force Parse y en la caja de texto input introducimos la expresión a comprobar.
( x + y) –x

acepta la expresión con el siguiente arbol

(x+y)-z
( x + y ) * x – z

Acepta la expresión con el siguiente árbol

(x+y)*x-z

(( x + y ) / z)

Acepta la expresión con el siguiente árbol.

((x+y)/z)

((x+y)(x+z))

Rechaza la expresión

( x + y ) * x – z * y / ( x + x )

Al verificar la expresión utilizando brute force parse se satura es espacio del Heap por lo que no se puede verificar, si transformamos la gramática en una gramática lineal por la derecha y en un autómata finito podemos verificar si la expresión es valida en el automata.

Rechaza la expresión.

3. Describir el lenguaje generado por las siguientes reglas de producción
S → SS | aSb | bSa | ab | ba

ffff

4. Modelar e introducir en JFLAP la siguiente gramática básica de un idioma.

a. <frase> → <sujeto> <predicado>
b. <sujeto> → <articulo> <sustantivo>
c. <articulo> → el | la
d. <sustantivo> → mundo | río | niña
e. <predicado> → <verbo>
f. <verbo> → fluye | gira | llora

Forma todas las frases correctas

el mundo fluye
el mundo gira
el mundo llora
el río fluye
el río gira
el río llora
la niña fluye
la niña gira
la niña llora

Intenta crear una gramática más compleja, para expresar frases como.
El lado oculto de la luna permanece inexplorado
Las prácticas de TALF son entretenidas…

Hoja 9 (27 de Abril de 2010)

P1: Minimiza el siguiente autómata finito determinista. El estado inicial es el estado a.

autómata no minimizado

autómata inicial

Paso 1: eliminamos estados no accesibles.

Un estado no accesible es un estado que no esta relacionado con el conjunto de estados al que pertenece el estado inicial o perteneciendo a este no tiene símbolos de entrada solo de salida. en este caso eliminamos el elemento i, al eliminar el estado i el estado d queda sin símbolos de entrada por lo tanto d tampoco es accesible.

estados no alcanzables eliminados

Paso 2: construimos la matriz de estados

matriz de estados

X/X ^a b *c e f g h
^a “” “” “” “” “” “” “”
b “” “” “” “” “” “” “”
*c “” “” “” “” “” “” “”
e “” “” “” “” “” “” “”
f “” “” “” “” “” “” “”
g “” “” “” “” “” “” “”
h “” “” “” “” “” “” “”

cada estado es equivalente entre si por lo tanto los descartamos de la misma forma que un triangular de la matriz

X/X ^a b *c e f g h
^a ~ “” “” “” “” “” “”
b ~ ~ “” “” “” “” “”
*c ~ ~ ~ “” “” “” “”
e ~ ~ ~ ~ “” “” “”
f ~ ~ ~ ~ ~ “” “”
g ~ ~ ~ ~ ~ ~ “”
h ~ ~ ~ ~ ~ ~ ~

un estado no final no va a ser equivalente a un estado no final por lo tanto marcamos las celdas donde se relacione un estado final y uno no final

X/X ^a b *c e f g h
^a ~ “” X “” “” “” “”
b ~ ~ X “” “” “” “”
*c ~ ~ ~ X X X X
e ~ ~ ~ ~ “” “” “”
f ~ ~ ~ ~ ~ “” “”
g ~ ~ ~ ~ ~ ~ “”
h ~ ~ ~ ~ ~ ~ ~

llegados a este punto comenzamos a emparejar los estados no marcados:

  • (a,b) X
    • con 0 vamos a (b,g) no esta marcado no hacemos nada
    • con 1 vamos a (f,c)  esta marcado por lo tanto marcamos (a,b)
  • (a,e) X
    • con 0 vamos a (b,h)  esta en la diagonal principal no hacemos nada
    • con 1 vamos a (f,f)   esta en la diagonal principal no hacemos nada
    • quedamos a la espera de lo que suceda cuando miremos (b,h)
  • (a,f) X
    • con 0 vamos a (b,c) como esta marcado marcamos (a,f)
    • con 1 vamos a (f,g) como no esta marcado no hacemos nada
  • (a,g) X
    • con 0 vamos a (b,g) como no esta marcado ni no comprobado esperamos a lo que suceda al comprobar (b,g)
    • con 1 vamos a (f,e) que no esta marcado no hacemos nada
  • (a,h) X
    • con 0 vamos a (b,c) como esta marcado marcamos (a,h)
    • 1 no lo miramos porque (a,h) ya se ha marcado
  • (b,e) X
    • con 0 vamos a (g,h) como no esta marcado no hacemos nada.
    • con 1 vamos a (c,f) como esta marcado marcamos (b,e)
  • (b,f) X
    • con 0 vamos a (g,c) como (c,g) esta marcado marcamos (b,f)
    • 1 no lo miramos porque (b,f) ya se ha marcado.
  • (b,g) X
    • con 0 vamos a (g,g) como esta en la diagonal principal no hacemos nada
    • con 1 vamos a (c,e) como esta marcado marcamos (b,g)
    • (a,g) estaba a la espera de (b,g) como (b,g) se ha marcado también marcaremos (a,g)
  • (b,h) X
    • con 0 vamos a (g,c) como (c,g) ya esta marcado marcamos (b,h)
    • 1 no lo miramos porque (b,h) ya se ha marcado
    • (a,e) estaba a la espera de (b,h) como lo hemos marcado marcamos también (a,e)
  • (e,f) X
    • con 0 vamos a (h,c)  como (c,h) esta marcado marcamos (e,f)
    • 1 no lo miramos porque (e,f) ya esta marcado
  • (e,g) X
    • con 0 vamos a (h,g) o (g,h) como no esta marcado ni comprobado esperamos a comprobar (g,h)
    • con 1 vamos a (f,e) o (e,f) como  esta marcado marcamos (e,g)
    • marcamos también (d,f) y (d,h) porque estaban a la espera de (e,g)
  • (e,h) X
    • con 0 vamos a (h,c) como (c,h) esta marcado marcamos (e,h)
    • 1 no lo miramos porque (e,h) ya se ha marcado
  • (f,g) X
    • con 0 vamos a (c,g) como ya esta marcado marcamos (f,g)
    • 1 no lo miramos porque ya hemos marcado (f,g)
  • (f,h)
    • con 0 vamos a (c,c) como esta en la diagonal principal lo obviamos
    • con 1 vamos a (g,g) como esta en la diagonal principal lo obviamos
  • (g,h) X
    • con 0 vamos a (g,c) como (c,g) esta marcado marcamos (g,h)
    • 1 no lo miramos porque ya hemos marcado (g,h)

Finalmete la matriz queda de la siguiente forma

X/X ^a b *c e f g h
^a ~ X X X X X X
b ~ ~ X X X X X
*c ~ ~ ~ X X X X
e ~ ~ ~ ~ X X X
f ~ ~ ~ ~ ~ X “”
g ~ ~ ~ ~ ~ ~ X
h ~ ~ ~ ~ ~ ~ ~

las casillas no marcadas indican estados equivalentes en este caso solo tenemos una casilla no marcada que es (f,h) que nos indica que f es equivalente a h quedando el autómata mínimo de esta forma:

autómata mínimo

nuestro autómata mínimo esta formado por 7 estados  para comprobar si la minimización  esta bien realizada minimizamos el automata original en JFlap y comparamos su equivalencia y el numero de estado del autómata mínimo generado, el automata minimo generado es el siguiente:

autómata mínimo jflapel numero de estados es el mismo el los dos autómatas y el lenguaje generado es equivalente  por lo que debería de estar bien

P2: Determina el Indice(RL) del lenguaje definido por una expresión regular sobre el alfabeto {a, b, c} que define todas las palabras que tengan por lo menos dos a’s consecutivas o por lo menos dos b’s consecutivas (mira hoja 6 si quieres).

Para saber el indice  (RL) de la expresión regular  tenemos que realizar el siguiente proceso de conversión
Expresión Regular –> AFND-ε –> AFND —> AFD —> AFD mínimo

la expresión regular es (a + b + c)∗ (aa + bb)(a + b + c)∗

el numero de estados del AFD minimo sera el indice del RL en caso que sea completo sino tenemos que sumarle 1 por el estado de error

Paso 1 Expresión Regular a AFND-ε:
Para realizar esta conversión nos basamos en los cinco casos básicos:

  • caso 1:para caso “A”Regla 1 expresión regular a AFND
  • regla 2:para caso  “epsilon”Regla 2 expresión regular a AFND
  • regla 3:para caso “AB”Regla 3 expresión regular a AFND
  • regla 4:para caso “A+B”Regla 4 expresión regular a AFND
  • regla 5:para caso “A*”Regla 5 expresión regular a AFND

Dividimos la expresión regular en los subconjuntos mínimos a generando un árbol de descomposición.

árbol derivación expresión regularempezamos a modelar desde el segundo nivel ya que el primero es muy sencillo

(a+b+c)*

(a+b+c)*

(aa+bb)

(aa+bb)

unimos los autómatas del segundo nivel y generaremos el automata que describe la expresión regular (a + b + c)∗ (aa + bb)(a + b + c)∗.

AFND from REGEXPcomparamos con el JFlap y son equivalentes por lo tanto este paso va bien, ahora eliminamos las transiciones epsilon.

AFND TO AFDY el AFD generado lo minimizamos

AFD Mínimocomo es completo el indice(RL) es igual a 4 , si no fuera completo habría que añadir el estado de error siendo el indice(RL) igual al numero de estados del AFD mínimo + el estado de error

Practica 7 Conversiones Autómatas lenguajes regexp en JFlap

El enunciado de la practica aqui:Practica 7 TALF

1.-Encuentra el AFD mínimo que reconoce el lenguaje representado por la expresión regular (RegEx) siguiente (00+10*1+λ)*(1+00)

En JFlap escogemos la opción de expresión regular

1 1 expresion regularintroducimos la expresión regular en el cuadro de dialogo

1 2 expresion regular

seleccionamos la opción Convert to NFA del menu convert para convertir una expresión regular en un autómata finito no determinista lo que nos creara el siguiente AFND

1 3 autómata finito no deterministaConvertimos el AFND en un AFD usando  la opción “Convert to DFA” del menú Convert

1 4 automata finito deterministacomo ultimo paso debemos minimizar el autómata finito determinista la opción para realizar la minimización se encuentre en el menú Convert  en la opción minimize DFA

1 5 automata finito determinista minimo

2.-Encuentra el AFD mínimo que reconoce el lenguaje representado por la siguiente gramática, y comprueba si es equivalente al del ejercicio anterior

S → 0A
S → 1C
D → 1C
B → 0B
C → 1S
D → 0A
A → 0D
C → 0B
B → 1S
S →1
D→1
A→0

Introducimos la gramática en JFlap

1 Gramatica Introducida

Pinchamos en Convert –> Convert Right Lineal Grammar to FA nos aparece una ventana donde introducimos la siguiente secuencia Show all -> Done? –> Export

2 Conversion a FA

Aparece una nueva Ventana con el FA generado
3 FA Convertido

Seleccionamos el menu test -> compare equivalence –> seleccionamos el AFD minimo del apartado anterior

4 equivalencia

son equivalentes

3.-Encuentra una expresión regular y una gramática para el lenguaje reconocido por el autómata siguiente

1 automatapara convertir el autómata en una expresión regular seleccionamos la opción “convert FA to RE” del menú “convert” que nos obligara a añadir un estado final que no sea inicial quedando de la siguiente forma

autómata a expresión regular

pinchamos en el botón “Do It” hasta que realice todos los pasos necesarios para la conversión informándonos en este punto con un mensaje con el siguiente text “You’re done. Go away.”  momento en el que pincharemos en export que nos mostrara la expresión regular en una nueva ventana.

(b(ab)*+(a+b(ab)*(b+aa))(ba+(a+bb)(ab)*(b+aa))*(a+bb)(ab)*)*

(b(ab)*+(a+b(ab)*(b+aa))(ba+(a+bb)(ab)*(b+aa))*(a+bb)(ab)*)*

para convertir el autómata en una gramática en la ventana del autómata seleccionamos “Convert to Grammar” en el menú “Convert”   y presionamos repetidamente el botón “Hint” repetidas veces hasta que genere la gramática

conversión a gramática

una vez generada la gramática solo resta pulsar en el botón Export que abrirá una nueva ventana con la gramática

gramática

4.-Comprueba que el autómata anterior es equivalente a la siguiente Expresión Regular ((aa+b)(ba)*(a+bb+λ)+ab)*(aa+b)(ba)*+λ

JFlap no puede compara equivalencia entre expresiones regulares por lo tanto debemos transformar la expresión regular en un autómata para eso creamos una nueva expresión regular en JFlap

expresión regular

una vez insertada la expresión regular  seleccionamos la opción “Convert to NFA”  del menú “Convert”

regexp to AFN

Una vez generado el AFND solo necesitamos comprobar la equivalencia en el menú “Test” -> “Compare Equivalence” que nos dirá que son equivalentes, en este caso son equivalentes

AFN