Tag: universidade

Posted on

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

Posted on

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

Posted on

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

Posted on

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

Posted on

P4: Configuración de una plataforma de desarrollo de aplicaciones basadas en web

El objetivo de esta práctica es instalar en una máquina todos los servicios necesarios para desarrollar un proyecto web basado en PHP y MySQL.

Primer Apartado:

  1. Instalación y configuración de Apache
  2. Instalación y configuración de PHP
  3. Instalación de MySQL
  4. Instalación de phpMyAdmin

Segundo Apartado (archivo de configuración de Apache):

5. Comentar brevemente qué debemos realizar para que Apache ejecute correctamente páginas escritas en PHP.

una vez configurado apache debemos instalar PHP con los módulos que necesitemos y en caso de no utilizar un instalador automático debemos indicarle al servidor apache los parámetros de configuración para que cargue el interprete PHP y configurar las variables necesarias para eso basta con introducir las siguientes directivas:
PHPIniDir ruta <– indica la carpeta donde se encuentra el archivo php.ini que nos permite configurar el comportamiento de PHP
LoadModule “ruta a la librería php5apache2_2.dll que contiene el modulo php” <– indica la librería donde se encuentra compilado el modulo de php y ordena al servidor apache cargarlo
Si todos los parámetros introducidos son correctos basta con reiniciar el servidor apache para que este vuelva a leer el archivo de configuración y pueda comenzar a interpretar las paginas PHP.

6. Respecto al archivo de configuración de Apache (httpd.conf):

  • a. ¿qué objetivo tiene la sección de DirectoryIndex? Pon un ejemplo y coméntalo.
    • Establece el archivo a proporcionar cuando el navegador proporciona una ruta incompleta, por ejemplo  la conexión a http://httpd.apache.org/docs/1.3/mod/ enviara la pagina http://httpd.apache.org/docs/1.3/mod/index.html siempre y cuando exista ese fichero y en la lista de  DirectoryIndex la subcadena index.html este antes de cualquier archivo existente, en caso de que no  exista ningun archivo en la lista de cadenas la respuesta a la petición sera el contenido del directorio, (en caso de que existan restricciones en el contenido del directorio se mostrara una pagina forbidden).
  • b. ¿dónde especificarías una capeta distinta a htdocs para servir archivos?
    • Si lo que queremos es utilizar una carpeta distinta a la que viene configurada por defecto simplemente debemos de cambiar el valor asociado a la directiva DocumentRoot  especificándole la carpeta donde queremos situar la raíz del servidor httpd, hemos de recordar que el usuario asociado al servidor apache tenga los permisos garantizados en caso contrario sufrirá un error de acceso denegado.
  • c. ¿para qué sirve el parámetro Timeout?
    • Timeout es una directiva que establece un contador en segundos que apache usara para gestionar los tiempos máximos de espera para:
      • tiempo de espera para una petición get .
      • tiempo de espera para la recepción de paquetes TCP en una petición POST o PUT .
      • tiempo de espera para enviar un ACK para un paquete TCP.
  • d. ¿cómo configurarías el servidor para un puerto distinto del 80?
    • Abrimos el archivo httpd.conf y reemplazamos la linea que pone Listen 80 por Listen “puerto deseado”.

Tercer Apartado (archivo de configuración de PHP):

7. Descripción del parámetro error_reporting. Pon algún ejemplo

La directiva error_reporting define el nivel de informe de errores se puede establecer con los valores de la siguiente lista:

  • E_ERROR            1    Informa de errores en tiempo de ejecución, como problemas de asignación de memoria. detiene la ejecución del código
  • E_WARNING        2    Informa de advertencias en tiempo de ejecución (no errores fatales), la ejecución del script no se detiene
  • E_PARSE            4    Informa de errores del analizador sintáctico. Estos errores son solo generados por el analizador sintáctico
  • E_NOTICE        8    Informa de avisos en tiempo de ejecución. Podría indicar que algo encontrado es un error pero el aviso puede ser generado por la ejecución esperada del script
  • E_CORE_ERROR        16    Informa de errores fatales que ocurren durante el arranque de PHP. Es como E_ERROR excepto que solo son generados por el núcleo de php
  • E_CORE_WARNING        32    Informa de advertencias (no errores fatales) que ocurren en el arranque de PHP. Es como E_WARNING excepto que las advertencias son las generadas por el núcleo de php
  • E_COMPILE_WARNING    128    Informa de advertencias (no errores fatales). Esto es como E_WARNING, solo que las advertencias son geradas por en motor de Scripting Zend
  • E_USER_ERROR        256    Mensajes de error generados por el usuario. Esto es como E_ERROR, excepto que es generado en el código PHP por la función trigger_error()
  • E_USER_WARNING        512    Advertencias de error generados por el usuario, Es como E_WARNING, excepto que es generado en el código PHP por la función trigger_error()
  • E_USER_NOTICE        1024    Avisos generados por el usuario. Es como E_NOTICE, excepto que es generado en el código PHP por la función trigger_error()
  • E_STRICT        2048    Habilita las sugerencias de cambios de PHP , que se aseguran de obtener de la mejor interoperatividad entre versiones de PHP
  • E_RECOVERABLE_ERROR    4096    Errores fatales recuperables. Estos indican la probabilidad de que un error peligroso ocurra, pero no dejara el motor en un estado inestables. Si este error no es gestionado por un manejador definido por el usuario la ejecución de la aplicación se abortara como si fuera un E_ERROR.
  • E_DEPRECATED        8192    Avisos en tiempo de ejecución. Activar este nivel informara de advertencias sobre codigo que no funcionara en futuras versiones
  • E_USER_DEPRECATED    16384    Avisos en tiempo de ejecución generados por el usuario. Funciona como E_DEPRECATED, excepto que son generados en el código PHP usando la funcion trigger_error()
  • E_ALL            30719    Informa de todos los errores y Advertencias, siempre que estén soportadas, exceptuando el nivel E_STRICT.

Ejemplos: Si queremos verificar la compatibilidad de nuestro codigo con futuras versiones de PHP deberiamos de activar E_DEPRECATED.
En modo de depuración es recomendable activar la opción E_ALL.
Si nuestro codigo informa de errores que desencadenan otros errores, tal vez nos interese filtrar activando las opciones E_USER_***
8. ¿qué importancia tiene el parámetro register_globals?

Habilita o deshabilita el reistro de las variables de entorno, GET, POST, Cookie y Servidor como variables globales. No es recomendable habilitarlo ya que no forma parte de las buenas practicas de programación y es inseguro.

9. ¿qué objetivo tiene la sección de File Uploads? Comenta sus parámetros.

Permite la recepción de archivos en el servidor usando el protocolo HTTP. los parámetros son:

  • file_uploads = booleano habilita o deshabilita la recepción de archivos
  • upload_tmp_dir= especifica un directorio temporal para la recepción de archivos
  • upload_max_filesize = XXM acota el tamaño máximo de los archivos que puede recibir el servidor.

Cuarto Apartado:
10. Una vez instalados todos los servicios en la máquina, el alumno deberá realizar lo siguiente:
11. Crear una base de datos y tabla con unos datos de ejemplo utilizando phpMyAdmin

Para crear una base de datos en phpMyAdmin primero accedemos a la url donde esta instalado phpMyAdmin, en este caso . Una vez en la dirección aparecerá un formulario solicitándonos el nombre de usuario y la contraseña

Ventana Login PhpMyAdminintroducimos el nombre y la contraseña para un usuario con privilegios en la creación de bases de datos.

Una vez identificados en el phpMyAdmin para crear la base de datos seleccionamos la pestaña base de datos y en el campo “Crear nueva base de datos” introducimos el nombre de la base de datos que queremos crear.

Crear Nueva base de datos phpMyAdmin

al pinchar en Crear phpMyAdmin ejecutara el siguiente comando SQL

CREATE DATABASE `practicaCSI4` ;

para crear las tablas en la base de datos navegamos hasta la pagina de información de la base de datos practicaCSI4 y en la pestaña estructura introducimos el numero de campos y el nombre de la tabla que queremos añadir a la base de datos.

Crear Nueva tabla phpMyAdminnos llevara a una pagina donde definiremos los campos de la base de datos.

definiendo campos de una tabla phpMyAdminuna vez hayamos cubierto el formulario pulsaremos el boton gravar que creara la tabla insertando el siguiente comando SQL


CREATE TABLE `practicacsi4`.`personas` (
`nombre` VARCHAR( 50 ) NOT NULL ,
`apellidos` VARCHAR( 50 ) NOT NULL ,
`direccion` VARCHAR( 200 ) NOT NULL ,
`codigopostal` INT NOT NULL ,
`provincia` VARCHAR( 15 ) NOT NULL ,
`dni` VARCHAR( 9 ) NOT NULL ,
`fechaNacimiento` DATE NOT NULL
) ENGINE = InnoDB

Repetimos el proceso para la segunda tabla

definiendo campos a tabla 2 phpMyAdminla creación de la segunda tabla generara el siguiente comando SQL

CREATE TABLE `practicacsi4`.`noticias` (
`titular` VARCHAR( 120 ) NOT NULL ,
`entradilla` VARCHAR( 400 ) NOT NULL ,
`texto` VARCHAR( 4000 ) NOT NULL ,
`fecha` DATE NOT NULL ,
`firma` VARCHAR( 200 ) NOT NULL ,
`fuente` VARCHAR( 180 ) NOT NULL ,
`foto` VARCHAR( 100 ) NOT NULL ,
PRIMARY KEY ( `titular` )

12. Crear una página sencilla en php que realice la conexión con la base de datos y muestre los resultados en pantalla

Se hace en la próxima practica.

13. Facilitar al profesor una URL a través de la cual pueda visualizar la página y otra URL a través de la cuál pueda acceder a phpMyAdmin y realizar cambios en la base de datos de tal manera que esos cambios aparezcan reflejados al consultar de nuevo la página.

Acceso a phpMyAdmin:

Las tablas de base de datos a crear pueden ser:

A) Ficha de datos personal con lo siguientes campos:

  • a. Nombre
  • b. Apellidos
  • c. Dirección
  • d. Código Postal
  • e. Provincia
  • f. DNI
  • g. Fecha de Nacimiento

B) Ficha de datos de una sección de noticias:

  • a. Titular
  • b. Entradilla
  • c. Texto
  • d. Fecha
  • e. Firma
  • f. Fuente
  • g. Foto (opcional)
Posted on

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…

Posted on

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

Posted on

Hoja 8 (20 de Abril de 2010)

P1: Sea C = {a,b,c,d,e,f,g,h} un conjunto (de letras), y sea R = {(a, d), (b, e), (c, a), (d, b), (e, c), (f, g), (g, h)} ⊂ C × C una relación sobre C.

  • Construye las relaciones Ri para todos los i = 0, . . . , ∞.
    • R0 ={(a,a),(b,b),(c,c),(d,d),(e,e),(f,f),(g,g),(h,h)}   (Las relaciones de todos los elementos consigo mismo)
    • R1={(a,d),(b,e),(c,a),(d,b),(e,c),(f,g),(g,h)} (La relación que nos dan)
      • (a,d) de R1  y (d,b) de R1 generan (a,b).
      • (b,e) de R1 y (e,c) de R1 generan (b,c).
      • (c,a) de R1 y (a,d) de R1 generan (c,d).
      • (d,b) de R1 y (b,e) de R1 generan (d,e).
      • (e,c) de R1 y (c,a) de R1 generan (e,a).
      • (f,g) de R1 y (g,h) de R1 generan (f,h).
      • (g,h) de R1 no genera nada.
    • R2={(a,b),(b,c),(c,d),(d,e),(e,a),(f,h)} <–( la unión de las relaciones generadas en R1)
      • (a,b) de R2 y (b,e) de R1  generan (a,e).
      • (b,c) de R2 y (c,a) de R1 generan (b,a).
      • (c,d) de R2 y (d,b) de R1 generan (c,b).
      • (d,e) de R2 y (e,c) de R1 generan (d,c).
      • (e,a) de R2 y (a,d) de R1 generan (e,d).
      • (f,h) de R2  no genera nada
    • R3={(a,e),(b,a),(c,b),(d,c),(e,d)} <– ( la unión de las relaciones generadas en R2)
      • (a,e) de R3 y (e,c) de R1 generan (a,c).
      • (b,a) de R3 y (a,d) de R1 generan (b,d).
      • (c,b) de R3 y (b,e) de R1 generan (c,e).
      • (d,c) de R3 y (c,a) de R1 generan (d,a).
      • (e,d) de R3 y (d,b) de R1 generan (e,b).
    • R4={(a,c),(b,d),(c,e),(d,a),(e,b)} <– (la unión de las relaciones generadas en R3)
      • (a,c) de R4 y (c,a) de R1 generan (a,a).
      • (b,d) de R4 y (d,b) de R1 generan (b,b).
      • (c,e) de R4 y (e,c) de R1 generan (c,c).
      • (d,a) de R4 y (a,d) de R1 generan (d,d).
      • (e,b) de R4 y (b,e) de R1 generan (e,e).
    • R5={(a,a),(b,b),(c,c),(d,d),(e,e)} <– (la unión de las relaciones generadas en R4)
      • (a,a) de R5 y (a,d) de R1 generan (a,d).
      • (b,b) de R5 y (b,e) de R1 generan (b,e).
      • (c,c) de R5 y (c,a) de R1 generan (c,a).
      • (d,d) de R5 y (d,b) de R1 generan (d,b).
      • (e,e) de R5 y (e,c) de R1 generan (e,c).
    • R6={(a,d),(b,e),(c,a),(d,b),(e,c)} <– (la unión de las relaciones generadas en R5)
      • (a,d) de R6  y (d,b) de R1 generan (a,b).
      • (b,e) de R6 y (e,c) de R1 generan (b,c).
      • (c,a) de R6 y (a,d) de R1 generan (c,d).
      • (d,b) de R6 y (b,e) de R1 generan (d,e).
      • (e,c) de R6 y (c,a) de R1 generan (e,a).
    • R7={(a,b),(b,c),(c,d),(d,e),(e,a)} <– (la unión de las relaciones generadas en R6)
      • (a,b) de R7 y (b,e) de R1  generan (a,e).
      • (b,c) de R7 y (c,a) de R1 generan (b,a).
      • (c,d) de R7 y (d,b) de R1 generan (c,b).
      • (d,e) de R7 y (e,c) de R1 generan (d,c).
      • (e,a) de R7 y (a,d) de R1 generan (e,d).
    • R8={(a,e),(b,a),(c,b),(d,c),(e,d)} ==R3 <– (la unión de las relaciones generadas en R7)
    • R9==R4
    • R10=R5
    • R11=R6
    • R12=R7
    • R13=R3
    • Rn=  R (n-3) mod 5+3
  • Construye la relación R∗.

Basta con unir todas las relaciones hasta R5 ( a partir de R7 el resto estarán repetidas y R5,R6 y R7 son subconjuntos)

R*={(a,a),(b,b),(c,c),(d,d),(e,e),(f,f),(g,g),(h,h),(a,d),(b,e),(c,a),(d,b),(e,c),(f,g),(g,h),(a,b),(b,c),(c,d),(d,e),(e,a),(f,h),(a,e),(b,a),(c,b),(d,c),(e,d),(a,c),(b,d),(c,e),(d,a),(e,b)}

  • Argumenta si R∗ es reflexiva, simétrica , y/o transitiva.
    • Reflexiva: Si porque todo elemento estan relacionados consigo mismo al pertenecer R0 a R*.
    • Simétrica:
      • (a,d) y (d,a) V
      • (b,e) y (e,b) V
      • (c,a) y (a,c) V
      • (d,b) y (b,d) V
      • (e,c) y (c,e) V
      • (f,g) no existe (g,f) F
      • (g,h) no existe (h,g) F
      • (a,b) y (b,a) V
      • (b,c) y (c,b) V
      • (c,d) y (d,c) V
      • (d,e) y (e,d) V
      • (e,a) y (a,e) V
      • (f,h) no existe (h,f) F
    • Transitiva: Si, porque hemos relacionado todas los pares entre si
  • ¿Cuál pareja (o parejas) deberíamos añadir a la relación R para que R∗ sea simétrica (si piensas que R∗ no es simétrica en el apartado anterior)?
    • (g,f), (h,g) y (h,f)
Posted on

Hoja 7 (13 de Abril de 2010)

P1: Determina una expresión regular α que define el mismo lenguaje aceptado por el autómata de la Hoja 5, digamos M , es decir, se tiene que cumplir L(α) = L(M ). Documenta tu construcción suficientemente (tienes dos lados de una hoja).

partimos del autómata de la hoja 5

Automata Inicialpara transformar nuestro AFND en una expresión regular necesitamos crear un AFNDG que este cumpla una serie de caracteristicas:

  1. El estado inicial no puede tener transiciones entrantes.
  2. El estado inicial debe de contar con transiciones salientes a los otros estados.
  3. Solo puede existir un estado final.
  4. El estado final no puede tener transiciones salientes.
  5. El estado final tiene que recibir transiciones entrantes de los otros.
  6. Excepto los estados inicial y final, cada estado tiene una única transición a los otros estados.

Transformando un AFND a un AFNDG

  1. Añadimos un nuevo estado inicial s con una transición epsilon  al viejo estado inicial.
  2. Añadimos un nuevo estado final f con transiciones epsilon entrantes de los viejos estados finales.
  3. Si dos estados están conectados con múltiples transiciones, las reemplazamos por una única transición en la que su etiqueta es la unión de las etiquetas reemplazadas.
  4. Si dos estados no están conectados, añadimos una transición etiquetada con ∅ entre ellos (en ambas direcciones).
  • Las transiciones ∅ nunca serán usadas.

Empezamos la transformación.

Paso 1:

AFND a AFNDG paso 1Paso 2:

AFND a AFNDG paso 2

Paso 3:

No existen multiples transiciones que conecten 2 estados nuestro automata sigue como esta.

Paso 4:

Vamos a dejar las transiciones ∅ sin poner.

De AFNDG a Expresión Regular

Para convertir un AFNDG con k estados en una expresión regular:

  1. Si k=2, solo tenemos los estados f y s. La etiqueta de la transición de s a f es la expresión regular equivalente al AFNDG
  2. Si k>2 , entonces construimos un AFNDG con k-1 estados.
    1. a) Escogemos un estado distinto de s y f.
    2. b) Eliminamos el estado seleccionado del autómata
    3. c) Reconectamos las transiciones sueltas de forma apropiada.
      1. Para cada par de estados, qi y qj, cambiamos la etiqueta de la transición por una que pueda tomar el AFNDG desde qi a qj de forma directa o a través del estado que estamos seleccionado

Comenzamos eliminando el estado marcado como 1

  • no tiene transiciones consigo mismo
  • las transiciones entrantes provienen  del estado  {s}
  • las transiciones salientes se dirigen a los estados {2,6}

por lo tanto debemos crear los transiciones {s,2} y {s,6}

  • la transición {s,2} es ε
  • la transición {s,6} es a

las modelamos en el automata

Estado 1 eliminado

no tenemos transiciones que tengan el mismo origen y destino continuamos

Eliminamos el estado marcado como 2:

  • tiene transiciones consigo mismo.
  • las transiciones entrantes provienen del conjunto de estados {s}
  • las transiciones salientes se dirigen a los estados {3,f}

por lo tanto tenemos que generar las transiciones {s,3} y {s,f}, como hay transición consigo mismo debemos ingresar (b)* en el medio

  • la transición {s,3} es (b)*.a
  • la transición {s,f} es (b)*

tras la eliminación del estado 2 nuestro autómata toma la siguiente forma

no tenemos transiciones que tengan el mismo origen y destino continuamos

Eliminamos el estado marcado como 3

  • no tiene transiciones consigo mismo
  • las transiciones entrantes provienen de {s,4,5}
  • las transiciones salientes se dirigen a {4,6}

por lo tanto debemos generar las transiciones {s,4},{s,6},{4,4},{4,6},{5,4},{5,6}

  • la transición {s,4} genera (b)*.aa
  • la transición {s,6} genera (b)*.a
  • la transición {4,4} genera b.a
  • la transición {4,6} genera b
  • la transición {5,4} genera a.a
  • la transición {5,6} genera a

tras la eliminación del estado 3 nuestro autómata toma la siguiente forma.

Estado 3 eliminado

tenemos transiciones con mismo origen y destino, {s,6} las unimos y nuestro autómata toma la siguiente forma

Estado 3 eliminado y transiciones

Eliminamos el estado marcado como 4

  • tiene transiciones consigo mismo
  • las transiciones entrantes provienen de {s,5,6}
  • las transiciones salientes se dirigen a{5,6,f}

por lo tanto debemos generar las transiciones {s,5},{s,6},{s,f},{5,5},{5,6},{5,f},{6,5},{6,6},{6,f} como 4 tiene transición consigo mismo tenemos que insertar (ba)* en el medio

  • la transición {s,5} genera (b)*aa(ba)*b
  • la transición {s,6} genera (b)*aa(ba)*b
  • la transición {s,f} genera (b)*aa(ba)*
  • la transición {5,5} genera aa(ba)*b
  • la transición {5,6} genera aa(ba)*b
  • la transición {5,f} genera aa(ba)*
  • la transición {6,5} genera (ba)*b
  • la transición {6,6} genera (ba)*b
  • la transición {6,f} genera  (ba)*

tras la eliminación del estado 4 nuestro autómata toma la siguiente forma.

Estado 4 eliminado

tenemos transiciones con el mismo origen y destino las unimos y nuestro autómata queda así

Estado 4 eliminado y transiciones

Eliminamos el estado marcado como 5

  • tiene transiciones consigo mismo
  • las transiciones entrantes provienen de {s,6}
  • Las transiciones salientes se dirigen  a {f,6}

las transiciones que debemos de crear son {s,f},{s,6},{6,f},{6,6} como  tiene transiciones consigo mismo debemos insertar (aa(ba)*b)* en medio

  • la transición {s,f} genera  (b)*aa(ba)*b(aa(ba)*b)*aa(ba)*
  • la transición {s,6} genera (b)*aa(ba)*b(aa(ba)*b)* (a+(aa((ba)*b)))
  • la transición {6,f} genera  (b+((ba)*b))(aa(ba)*b)*aa(ba)*
  • la transición {6,6} genera (b+((ba)*b))(aa(ba)*b)*(a+(aa((ba)*b)))

tras la eliminación del estado 5 nuestro autómata toma la siguiente forma

Estado 5 eliminadotenemos transiciones con el mismo origen y destino así que las unimos

la transición {s,6} quedara ((b)*aa(ba)*b(aa(ba)*b)*(a+(aa((ba)*b)))+((a+((b)*a))+(b)*aa(ba)*b)) ==s6

la transición {s,f} quedara (((b)*aa(ba)*b(aa(ba)*b)*aa(ba)*)+((b)*+(b)*aa(ba)*)) == sf

la transicion {6,6} quedara (((b+((ba)*b))(aa(ba)*b)*(a+(aa((ba)*b))))+((ba)*b)) == 66

la transición {6,f} quedara (((b+((ba)*b))(aa(ba)*b)*aa(ba)*)+((ba)*)) == 6f

Eliminamos el estado marcado como 6

  • tiene transiciones consigo mismo.
  • las transiciones entrantes provienen de {s}
  • las transiciones salientes se dirigen a {f}

por lo tanto deberemos de generar las transiciones {s,f} teniendo el cuenta como existe transición consigo mismo tenemos que insertar (66)* en medio

la transición {s,f} genera (sf)+((s6)(66)*(6f))

tras la eliminación del estado 6 nuestro autómata ya es la expresión regular.

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

introducimos a expresión regular en JFlap la transformamos es un AFND y comparamos la equivalencia con el AFNDG y………………………

Good Luck bad nigth

vamos que esta bien 🙂 a la 2ª fue la vencida

Fuentes:

http://vega.icu.ac.kr/~jiae/Automata_spring2008/DFA2RE.pdf

Posted on

Hoja 6 (6 de Abril de 2010)

P1: ¿Qué lenguajes definen las siguientes expresiones regulares?

  • Expresión regular numero 1: (((0.1)∗ + (0.1)∗ .0) + ((1.0)∗ + (1.0)∗ .1))
    Descomponemos la expresión regular

primera formula despiece webempezamos a descomponer la expresión regular a partir de los nodos finales (marcados en rojo).

Primera Formula Nodos finales marcadosPaso 1:  intentamos minimizar los nodos finales: en esta expresión no se puede

Paso 2:Describimos el lenguaje de cada nodo final:

  • :  cero o mas repeticiones  de la cadena 01
  • :cero o mas repeticiones de la cadena 01
  • : Cadena 0
  • formula 1 nodo final 4:cero o mas repeticiones de la cadena 10
  • formula 1 nodo final 5: Cadena 1

subimos al nivel anterior y unimos los nodos en los que sus elementos siguientes estén descritos hasta que lleguemos a la raíz del árbol.

formula 1 primera iteracion miramos si podemos minimizar los nodos a describir (marcados de rojo), en este caso no podemos.

asi que describimos los nodos en los que nos encontramos

  • formula 1 segunda interacion nodo 1: cero o mas repeticiones  de la cadena 01 unidas con 0
  • formula 1 segunda iteracion nodo 2:cero o mas repeticiones de la cadena 10 unidos con 1

nueva iteración. subimos al nivel superior

formula 1 tercera iteracion nodo 1

miramos si podemos minimizar los nodos a describir (marcados de rojo), en este caso no podemos.

asi que describimos los nodos en los que nos encontramos

  • formula 1 tercera iteracion nodo 1: cero o mas repeticiones de la cadena 01 ó cero o mas repeticiones  de la cadena 01 unidas con 0

subimos

ultima subida

Describimos la expresión regular  uniendo los elementos anteriores (+=0) (*=y)

cero o mas repeticiones de la cadena 01 ó cero o mas repeticiones  de la cadena 01 unidas con 0, o cero o mas repeticiones de la cadena 10 unidos con 1

Expresión regular numero 2: expresion regular numero dos

Paso 1: Descomponemos la expresión regular en pequeñas expresiones.

expresion regular numero 2 descompuesta

marcamos los nodos finales

expresion regular numero 2 nodos finalesMinimizamos los nodos finales, en este caso no se puede

Describimos los nodos finales

  • expresión_2_nodo_1:  la cadena 1 o nada
  • expresion numero 2 nodo 2: cero o mas repeticiones de la cadena 01
  • expresion 2 nodo 3:la cadena 0 o nada

subimos al siguiente nivel de la estructura

expresion regular numero 2 segunda iteracion

intentamos minimizar la expresión actual: no se puede

Describimos la expresión actual.

  • expresion regular numero dos:la cadena 1 o nada unida a cero o mas repeticiones de la cadena 01 unida a la cadena 0 o nada

  • Expresión regular numero 3 expresion regular numero 3

Paso 1: Descomponemos la expresión regular en pequeñas expresiones.

Arbol tercera expresion regular

marcamos los nodos finales

Arbol 3 era expresion nodos finales marcadosintentamo minimizar algún nodo final en este caso si que podemos

  • primera equivalencia
  • segunda equivalencia

empezamos a minimizar hacia arriba y nos queda la siguiente expresión minimizada

expresion regular numero 3 minimizada

describimos las expresiones del segundo nivel

  • minimizados primer elemento: la cadena 01
  • minimizado segundo elemento: cero o mas repeticiones de la cadena  con 0 o mas repeticiones de cero o de la cadena 01
  • : la cadena 1

por lo tanto el lenguaje que define esta expresión regular es: la cadena 01 o cero o mas repeticiones de la cadena  con 0 o mas repeticiones de cero o de la cadena 01 unido a la cadena 1

P2: Escribe una expresión regular sobre el alfabeto {a, b, c} que define todas las palabras que tengan dos a’s consecutivos o dos b’s consecutivos.

(a+b+c)*.((aa)+(bb)).(a+b+c)*

P3: Construye según procedimiento visto en clase un AFND–ε que acepta las mismas palabras que define la expresión regular de P1 apartado 2.
modelamos  las pequeñas expresiones el las que hemos descompuesto la expresión 2:

expresión_2_nodo_1

primer subautomata

expresion numero 2 nodo 2

2a_parte

expresion 2 nodo 3

Ahora unimos las partes en un autómata .