El sistema portaliano

1672 palabras 7 páginas
Autómatas finitos deterministas (AFD)
• Determinista: para cada entrada, existe un único estado al que el autómata puede llegar partiendo del estado actual • Consta de:

Tabla de transiciones
Representación tabular de la función " • filas: estados • columnas: entradas • estado inicial: flecha • estados finales: *
0 ->q0 q2 q1 q2 1 q0 q1 q1

Tema 2: Autómatas finitos

– un conjunto finito de estados, Q – un conjunto finito de símbolos de entrada, ! – una función de transición (") que, dados un estado y una entrada, devuelve un estado. "(q, a) = p – un estado inicial (uno de los estados de Q), q0 – un conjunto de estados finales o de aceptación (subconjunto de Q), F

• A = (Q, !, ", q0, F)

*q1 q2 Teoría de autómatas y
…ver más…
Acosta)

Tema 2: Autómatas finitos

6

© Manuel Mucientes (Revisión: Juan C. Acosta)

Tema 2: Autómatas finitos

Autómatas finitos no deterministas
• • • • • AFN: capacidad de estar en varios estados simultáneamente Aceptan los lenguajes regulares, igual que los AFD Más compactos y fáciles de diseñar que los AFD Siempre es posible convertir un AFN a un AFD Ejemplo: AFN que acepta las cadenas terminadas en 01

Ej: acepta la 00101?

© Manuel Mucientes (Revisión: Juan C. Acosta)

Tema 2: Autómatas finitos

10

Definición de los AFN
• A = (Q, !, ", q0, F) • " devuelve ahora un conjunto de estados, y no un solo estado

Construcción de subconjuntos
• Dado el AFN N= (QN, !, "N, q0, FN), obtener el AFD D= (QD, !, "D, {q0 }, FD) tal que L(D)=L(N)
– Alfabetos iguales – Estado inicial de D: conjunto con el estado inicial de N – QD: conjunto de subconjuntos de QN. Si QN tiene n estados, QD tendría 2n. (pueden simplificarse estados no accesibles a partir del inicial) – FD: conjunto de subconjuntos S de QN tales que S ' FN & % – Para cada S ( QN y cada símbolo de entrada a del alfabeto:

• Ejemplo: AFN que acepta las cadenas terminadas en 01
– A=({q0, q1, q2}, {0, 1}, ", q0, {q2}) 0 ->q0 {q0, q1} q1 q2 % % 1 {q0} {q2} %
Tema 2: Autómatas finitos 11

"D ( S , a ) #

p en S

!"

N

( p, a )

© Manuel Mucientes (Revisión: Juan C. Acosta)

© Manuel Mucientes (Revisión: Juan C. Acosta)

Tema 2:

Documentos relacionados

  • El sistema portaliano
    1684 palabras | 7 páginas
  • educacion en chile periodo conservador
    725 palabras | 3 páginas
  • Un Siglo De Historia Económica De Chile 1830-1930 Carmen Cariola Osvaldo Sunkel
    1299 palabras | 6 páginas
  • Ideologia Portaliana
    1135 palabras | 5 páginas
  • armando de ramon
    4112 palabras | 17 páginas
  • Prueba Formativa Regimen Parlamentario En Chile
    1821 palabras | 8 páginas
  • Resumen De El Peso De La Noche
    649 palabras | 3 páginas
  • Prueba De Historia De Chile
    1868 palabras | 8 páginas
  • Prueba De Historia De Chile
    1856 palabras | 8 páginas
  • Resumen Organizacion De La Republica
    3314 palabras | 14 páginas