Proceso de concatenación en DFA – Part 1

Requisito previo: diseñar autómatas finitos 
. Diseñar un DFA para el conjunto de strings sobre {a, b} de modo que las strings del lenguaje comiencen con «a» y terminen con «b». Allí se formarán dos idiomas deseados: 

L1 = {a, aab, aabab, .......}
L2 = {b, bbab, bbabab, .......} 

En L1, el elemento inicial es «a» y en L2, el elemento final es b. 

Diagrama de transición de estado para el idioma L1: 

Este DFA acepta toda la string que comienza con «a». Aquí, el estado C es el estado final y B es el estado muerto. Esto se llama así porque después de obtener cualquier alfabeto, este estado nunca irá al estado final. 

Diagrama de transición de estado para la lengua L2: 

Este DFA acepta todas las strings que terminan con el alfabeto «b». Aquí, el estado B se llama estado final. 

Ahora, tomando la concatenación del lenguaje L1 y L2 que da el resultado final del lenguaje que comienza con «a» y termina con «b». 

Diagrama de transición de estado de L1.L2, es decir, L1 concat L2:  

Este DFA acepta todas las strings que comienzan con a y terminan con b. Aquí, el estado C es el estado final y D es el estado muerto, este se llama así porque después de obtener cualquier alfabeto de entrada, nunca irá al estado final.
 

Publicación traducida automáticamente

Artículo escrito por Kanchan_Ray y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *