Tag: Universidad

Posted on

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

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

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

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

Practica 6 Talf

El enunciado aquí Practica 6 Talf

1.-Minimiza el autómata A1 = ({0,1},{q0, q1, q2, q3, q4}, f, q0,{q1, q2}) en donde f se define como:

  • f(q0, 0) = q3
  • f(q0, 1) = q2
  • f(q1, 0) = q4
  • f(q1, 1) = q1
  • f(q2, 0) = q0
  • f(q2, 1) = q3
  • f(q3, 0) = q0
  • f(q3, 1) = q2
  • f(q4, 0) = q4
  • f(q4, 1) = q1

modelamos el autómata en JFlap

modelado automata ejercicio 1para minimizarlo vamos al menu “Convert”->”minimize DFA”

minimizando paso 1obviamente los estados q1 y q4 quedan fuera porque no están asociados al grafo del estado inicial.

Pinchamos en el botón “Finish”

minimizado paso 2pinchamos en “complete” y en “done?” por lo que se mostrara el autómata minimizado en una nueva ventana

afd minimo

2. Indica cuáles de los siguientes autómatas son equivalentes entre sí:

  • AF1={{a,b},{p,q,r,s,t,u}, f1, p, {q,r}}
  • AF2={{a,b},{p,q,r,s,t,u}, f2, p, {u}}
  • AF3={{a,b},{p,q,r,s,t,u}, f3, p, {s,t,u}}
  • AF4={{a,b},{p,q,r,s,t,u}, f4, p, {r,s}}
  • AF5={{a,b},{p,q,r,s,t}, f5, p, {r,s}}

Autómata 1

F1 a b
p q p
q r s
r q t
s t u
t s u
u q u

modelamos el autómata en JFlap

automata 1

autómata 2

F2 a b
p q u
q r t
r s t
s r t
t u s
u u q

modelamos el autómata en JFlap

automata 2

autómata 3

F3 a b
p u q
q t r
r s r
s t r
t u q
u s p

modelamos el autómata en JFlap

automata 3

autómata 4

F4 a b
p r q
q r q
r s t
s r t
t t q
u u p

modelamos el autómata en JFlap

automata 4

autómata 5

F5 a b
p q r
q q t
r s q
s r q
t r q

modelamos el autómata en JFlap

automata 5

En la ventana de JFlap donde esta contenido el aútomata pintamos en “Test -> Compare Equivalence” y nos dice si es equivalente o no.

de la comprobación sacamos la siguiente tabla

@ AF1 AF2 AF3 AF4 AF5
AF1 – F F V F
AF2 – – F F V
AF3 – – – F F
AF4 – – – – F
AF5 – – – – –

Por lo tanto los autómatas equivalentes son AF1 con AF4 y AF2 con AF5