Teoria de la computacion

[pic 1]

PARCIAL DFA Y NFA

CODIGO TERMINADO EN 6

SERGIO DAVID BURBANO MARIÑO

C.C. 1007 655 316

PRESENTADO A
HERNANDO CASTAÑEDA MARIN

TEORIA DE LA COMPUTACION

UNIVERSIDAD DE PAMPLONA

INGENIERIA DE SISTEMAS

25 DE ABRIL. DE 2025

PAMPLONA, NORTE DE SANTADER

Descripción del problema

El problema consiste en construir un autómata no determinista (NFA) que acepte cadenas generadas por las siguientes expresiones regulares: la primera \( a(bb + bba)^* ba \), que describe cadenas que comienzan con "a", seguidas de una o más repeticiones de "bb" o "bba", y terminan con "ba"; y la segunda \( ab(bb + bab)^*a \), que describe cadenas que comienzan con "ab", seguidas de una o más repeticiones de "bb" o "bab", y terminan con "a". El autómata debe ser capaz de procesar estas cadenas de acuerdo a las transiciones definidas entre los estados, aceptando las cadenas que cumplen con las condiciones de las expresiones regulares y rechazando las que no las cumplen.5-TUPLA

A = (Q, Σ, δ, q₀, F)

• Q = {1,2,3,4,5, λ}
• Σ = {a, b}
• q₀ = {1}
• F = {5}
• δ (función de transición)

δ(1, a) = 2                 δ(1, b) = λ

δ(2, a) = λ                        δ(2, b) = 4

δ(3, a) = 2                 δ(3, b) = λ

δ(4, a) = 5                 δ(4, b) = δ(2, b) ∪ δ(3, b)

δ(5, a) = λ                 δ(5, b) = λ

EXPLICACIÓN DEL CODIGO

Ahora para interpretar código completo que implementa un autómata finito determinista (DFA) para aceptar cadenas que contienen exactamente una vez el substring aaa es necesario entender su funcionamiento con los métodos que son creados

[pic 2]

primero está la clase DFA que define cómo funciona el autómata

init: este método inicializa el autómata, recibe el conjunto de estados, alfabeto, función de transición, estado inicial y estados de aceptación. También establece el estado actual como el inicial

[pic 3]

transition_to_state_with_input: esta función hace la transición de un estado a otro dependiendo del símbolo que se está leyendo. Si no existe una transición para ese símbolo, cambia el estado actual a None, lo que indica un error.

[pic 4]

in_accept_state: verifica si el estado actual es uno de los estados de aceptación.

[pic 5]

go_to_initial_state: reinicia el estado actual al estado inicial.

[pic 6]

run_with_input_list: recibe una cadena (como lista de símbolos), reinicia el autómata, y luego va aplicando las transiciones para cada símbolo. Si termina en un estado de aceptación, devuelve True. Si en algún momento llega a un estado inválido (None), devuelve False.

...