• Categories
• Física y matemáticas
• Matemática
• Matemática aplicada
• Áreas de la informática
• Informática

Citation preview

UNIVERSIDAD NACIONAL DEL ALTIPLANO INGENIERÍA DE SISTEMAS

TRABAJO ENCARGADO: HERRAMIENTAS PARA SIMULACIÓN DE AUTOMATAS. ESTUDIANTE: - CHUPA QUISPE, Elmer Ramiro

PUNO – PERU 2012

DIFERENCIAS ENTRE THOTH Y JFLAP Ventajas del thoth

Ventajas de jflap 



Vista de la tabla de transición



Se puede hacer la equivalencia de



diagramado, en un autómata finito determinista

autómatas



conversión de un diagrama a un AFD

Se pude eliminar un AFND de



experimentación en otros lenguajes

manera rápida del diagrama del

formales como pushdown autómata no

autómata finito. 

Obtención

determinista, maquina multi-cinta de de

expresiones

regulares 

permite convertir un autómata finito

turing. 

Se puede validar si la cadena o

palabra pertenece al autómata y poder

palabra pertenece al autómata y poder

ver

los

pasos

que

ver los pasos que se siguieron para su

se

siguieron para su obtención. 

Menús llamativos al usuario



Facilidad de uso de los iconos en

Se puede validar si la cadena o

obtención. 

Posibilidad de guardar en distintos formatos de imagen.

interface Desventajas de thoth

Desventajas de jflap 

No se puede verificar si una cadena o palabra pertenece a un diagrama de autómata finito.

imagen

imagen

AUTOMATA FINITO (PARTE I) 1. Obtener la expresión regular que representa al lenguaje formado por todos las cadenas sobre {a,b} que tiene un numero par de bes, construir un diagrama de transición para ese lenguaje. Solución: a*b(ba*b)*ba*

2. Construir el diagrama de transición para el lenguaje dada por c*(a U bc*)*, convertir el diagrama en una función asociada al AFD etiquetando los estados. Solución:

a

b

C

1

2

1

1

2

2

1

-

3. Sea M={Q,Σ,s,F,δ} Q= {q0, q1, q2, q3} Σ= {1,2} F= {q0} s= q0

Analice: -

110101

-

011101

-

111011

-

011011

AUTOMATA FINITO (PARTE II) 1. Nombre de variable.

Diagrama de transiciones:

Tabla de transiciones:

l

D

1

3

2 (error)

2

-

-

3

3

3

Pseudocodigo: Estado=1 Lee(entrada) Mientras(no fin de cadena) Case(estado) 1 :si(simbolo=letra) Estado=3 sino si (simbolo=digito) Estado=2 Sino salir(error no reconocido) 2 : salir(error no reconocido) 3 : si(simbolo=letra) Estado=3 Sino si(simbolo=digito)

Estado=3

Sino salir(error no reconocido) Leer(siguiente simbolo) Si Estado diferente 1, 2, 3 salir(error no reconocido)

2. Número real.

D

+

Q0

Q1

Q1

Q1

Q2

Q3

Q3

Q3

Q4

Q6(error) Q5

Q5

Q6

Q6

Q6

Pseudocódigo: Estado= q0 Lee(entrada)

-

E

.

Q4

Q2

Q4 Q5

Mientras(no fin de cadena) Case(estado) q0 :

si(simbolo=d) Estado= q1 Sino salir(error no reconocido)

q1 :

si(simbolo=d) Estado= q1 Sino si(simbolo=.) Estado= q2 Sino si(simbolo=e) Estado= q4 Sino salir(error no reconocido)

q2 :

si(simbolo=d) Estado= q3 Sino salir(error no reconocido)

q3 :

si(simbolo=e) Estado= q4 Sino salir(error no reconocido)

q4 :

si(simbolo=-) Estado= q5 Sino si(simbolo=+) Estado= q5 Sino si(simbolo=d) Estado= q6 Sino salir(error no reconocido)

q5 :

si(simbolo=d) Estado= q6 Sino salir(error no reconocido)

q6 :

si(simbolo=d) Estado= q6 Sino salir(error no reconocido)

Leer(siguiente simbolo) Si Estado diferente q0, q1, q2, q3, q4, q5, q6 salir(error no reconocido) 3. Diseñar un diagrama de transiciones para reconocer expresiones aritméticas de longitud arbitraria que comprenden enteros positivos separados por signos de suma, resta, multiplicación o división. Solución:

d

*

+

-

/

Q0

Q0

Q1

Q1

Q1

Q1

Q1

Q0, Q2

Q2

Pseudocódigo: Estado= q0 Lee(entrada) Mientras(no fin de cadena)

Case(estado) q0 :

si(simbolo=d) Estado= q0 Sino si (símbolo=* o símbolo=+ símbolo=-

símbolo=/) Estado= q1 Sino salir (error no reconocido) q1 :

si(simbolo=d) Estado= q0/*********/ Sino si(simbolo=d) Estado= q2 Sino salir(error no reconocido)

q2 :

salir(error no reconocido)

Leer(siguiente simbolo) Si Estado diferente q0, q1, q2 Salir (error no reconocido)

AUTOMATA FINITO (PARTE III) 1. Diseñar un diagrama de transiciones para que te acepte expresiones: Variable = variable | variable {+,-,*./} variable | digito |

Diagrama de transiciones

δ

=

D

s

V

0 1

1 2

2

3

3

5

4

4 6 7

5

5

6

9

6

7

10

8 9 10

8

7 9

8

6 7

10

Pseudocodigo: Estado=0 Lee(entrada) Mientras(no fin de cadena) Case(Estado) 0 : si(simbolo=’V’) Estado=1 Sino salir(error no reconocido) 1 : si(simbolo=’=’) Estado=2 Sino salir(error no reconocido) 2 : si(simbolo=’D’) Estado=3 Sino si(simbolo=’V’) Estado=4 Sino salir(error no reconocido) 3 : si(simbolo=’D’) Estado=5 Sino si(simbolo=’S’) Estado=6 Sino salir(error no reconocido) 4 : si(simbolo=’V’) Estado=8 Sino si(simbolo=’S’) Estado=7 5 : si(simbolo=’D’) Estado=5 Sino si(simbolo=’S’) Estado=6 Sino salir(error no reconocido) 6 : si(simbolo=’D’) Estado=9 Sino salir(error no reconocido) 7 : si(simbolo=’V’) Estado=10 Sino salir(error no reconocido) 8 : si(simbolo=’V’) Estado=8 Sino si(simbolo=’S’) Estado=7 Sino salir(error no reconocido) 9 : si(simbolo=’D’) Estado=9 Sino salir(error no reconocido) 10 : si(simbolo=’V’)

Estado=10

Sino salir(error no reconocido) Leer(siguiente simbolo) Si Estado diferente 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 salir(error no reconocido)

2. Diseñar un diagrama de transiciones para un AFD que acepte exactamente aquellas cadenas X y Y, que contengan un numero par de X.

Diagrama de transiciones

y Q0

Q0

Q1

Q0

Q2

x

Q2 Q1

Pseudocódigo: Estado= q0 Lee(entrada) Mientras(no fin de cadena) Case(estado) q0 :

si(simbolo=Y) Estado= q1 o Estado= q0 Sino salir (error no reconocido)

q1 :

si(simbolo=Y) Estado= q1 Sino si(simbolo=X) Estado= q2 Sino salir(error no reconocido)

q2 :

Estado= q1

Si Estado diferente q0, q1, q2 Salir (error no reconocido)