Welcome, Guest
Username: Password: Remember me
  • Page:
  • 1

TOPIC: Materia vista sin apuntar hoy domingo

Materia vista sin apuntar hoy domingo 2 months 2 weeks ago #9167

  • kirstein
  • kirstein's Avatar Topic Author
  • Offline
  • Profesor
  • Profesor
  • Posts: 2694
  • Karma: 666
  • Thank you received: 1578
Hola,

+ Lo indicado.

Saludos,
Kirstein
-----------------------------------------------------------------------------
Autómatas de Dos vías.
-----------------------------------------------------------------------------
+ Definición y uso de Autómatas de 2 vías

Se basan en los AEFDs convencionales pero le dan la capacidad de mover la cabeza lectora a la izquierda o a la derecha, decidiéndolo en cada símbolo.

Sus siglas son A2V

Son máquinas reconocedoras (se basan en los AEFDs).

Hay dos símbolos <- -> que no son parte del alfabeto pero que ayudan a ese trabajo de los A2V.

Se diferencian de los AEFDs en el δ.
El resto de los componentes es similar (Q,q0,F,Σ)
δ:Q x Σ -> {<-,->} x Q 

Note que al permitir moverse a la izquierda además de a la derecha, la tira se puede terminar por ambos extremos.

Al permitir que la cabeza lectora vaya en ambas direcciones existe la posibilidad de ciclarse.

Para saber si se está enciclado hay que hacer una traza.

Si se cicla debe decir que NOp.

Observe la figura del A2V1

nnuu
si al salirse por la izquierda y terminar en q2
uunn
si al salirse por la derecha y terminar en q2
unun
si al salir por la derecha estando en q2 (y se movió 6 veces).
unnuu
se encicla y dice que no por eso.

  u  n  n  u  u
q0-q1-q2-q2-q3-
     -q1-q3-q3-  
     -q2

Nivel de poder computacional: Lenguajes Regulares.


+ Algoritmo AEFD -> A2V
Todos a la derecha (CAPITALISTAS!!!!).


+ Algoritmo A2V -> AEFD
Trazas.   Nivel 4.

---------------------------------------------------------------
Simplificación de AEFDs

Simplificar un AEFD consiste en encontrar otro AEFD que sea más eficiente y que se mantenga equivalente.

Un AEFD es equivalente a otro si reconoce el mismo lenguaje.

Un AEFD es más eficiente que otro, primero si tiene menos estados y como criterio de desempate si tiene menos transiciones.  Esto último aplica para los autómatas incompletos.

El algortimo de Simplificación que analizaremos se llama:
Algoritmo de Árbol de Clusters de Estados.


1. Se comienza el árbol con un solo cluster con todos los estados que pertenecen a Q

2. De esta raíz del árbol se crean dos clusters hijos, uno con los estados finales y otro con los estados no finales.

3. A partir de acá se analizan los destinos de cada uno de los estados del cluster para cada símbolo del alfabeto.  Si tiene destinos diferentes, se debe dividir el cluster en consecuencia.  Las partes del cluster pasan a ser hijos de ese cluster.

4.  Se termina cuando no se puede dividir ningún cluster adicional.  Cada cluster representa un estado del autómata simplificado.

5. El AEFD va a estar conformado por todas las hojas del árbol.

6. El estado inicial será el cluster que contenga al estado inicial original.

7. Los clusters ya están marcados claramente como finales y no finales.

8. Se cominenza a dibujar por el estado inicial y se van agregando al dibujo los estados a los que se llegan.  Habrá casos de clusters completos que no se utilizarán.  Estos son estados inalcanzables dentro del autómata.

9. A veces uno de los clusters generados es un hoyo negro.  Este puede eliminarse si se permite tener un autómata incompleto.

--------------------------------------------------------------
ERA -> ER

--------------------------------------------------------------
ER -> ERA
 Solo hay que ponerle un nombre a la ER.
--------------------------------------------------------------
¿A que nivel pertenecen los diagramas de tren?
Tren: Simples (no permiten recursividad).

Tren -> ER
1. El inicio y el final son comenzar y terminar la ER
2. Los círculos se traducen al símbolo directamente.
3. Los forks se traducen a ors (símbolo del más).
4. las líneas que conectan dos círculos directamente son concatenaciones.
5. Una línea de retorno que obliga a pasar por "la nubecita" es un X a la +
6. Una línea de retorno que pasa a través de una nube sobre una línea directa es el equivalente a X*
7. El orden de las líneas puede obligar a utilizar paréntesis para preservar el flujo de ejecución. 
8. Un vagón debe de expandirse en su representación directa (desencapsular).  Esto es posible solo si no existe recursividad.


  (e + 0 + 1)*

---------------------------------------------------------------------------
ER -> Tren

1. x es una ER si x es un símbolo del alfabeto.
Encerramos a x en un círculo.


2. El símbolo de vacío es una ER.  El conjunto vacío representa el lenguaje que no contiene ningún string.   Ø = { } 

()-----        -----||

3. epsilon representa la ER que define al conjunto que contiene solamente al string nulo. ε = { ε }

()------------------||

4. Son ER los resultados de combinar los siguientes operadores:
Usar nubecitas unidas sabiamente con los rieles.

4.1 Si A y B son ER A+B es una ER (or)
4.2 Si A y B son ER AB es una ER  (concatenación)
4.3 Si A es una ER A* es una ER  (cerradura de Kleene, repeticiones de 0 a N)
4.4 Si A es una ER A^+ es una ER (repeticiones de 1 a N)
4.5 Si A es una ER [ A ] es una ER (opcional)    
4.6 Si A es una ER y N un número natural A^N es una ER (cota superior) 
4.7 Si A es una ER (A) es una ER (los paréntesis son para quebrar la precedencia) : Encapsular.

-------------------------------------------------------------
ERA -> TR

1. Se debe convertir cada una de las definiciones de las ER de la ERA en su correspondiente tren.
2. Cada aparición de una invocación a una de las ER se traduce a un vagón.  
3. Como se trata de un Tren Recursivo no hay problema con que la ER sea recursiva.
4. Al final quedan tantos diagramas de tren independientes como ER tenía la ERA.

---------------------------------------------------------------------------
TR -> ERA

1. Cada Diagrama de un Tren Recursivo se traduce a una ER que tiene nombre.  
2. Los vagones se traducen a los nombres de las ER.
3. Se usa el mismo método de TR a ER.

----------------------------------------------------------------------------

The following user(s) said Thank You: josevillalobos

Please Identificarse to join the conversation.

Materia vista sin apuntar hoy domingo 2 months 2 weeks ago #9168

  • kirstein
  • kirstein's Avatar Topic Author
  • Offline
  • Profesor
  • Profesor
  • Posts: 2694
  • Karma: 666
  • Thank you received: 1578
Diagramas de ER a Tren

This message has an attachment file.
Please log in or register to see it.

Please Identificarse to join the conversation.

  • Page:
  • 1
  • Not Allowed: to create new topic.
  • Not Allowed: to reply.
  • Not Allowed: to add attachements.
  • Not Allowed: to edit your message.
Time to create page: 0.149 seconds
Powered by Kunena Forum