Requisito previo: diseño de autómatas finitos
Comprendamos el proceso de unión en autómatas finitos deterministas (DFA) con la ayuda del siguiente ejemplo.
Diseñar un DFA para el conjunto de strings sobre {a, b} de modo que la string del idioma comience y termine con diferentes símbolos. Allí se formarán dos idiomas deseados:
L1 = {ab, aab, aabab, .......}
L2 = {ba, bba, bbaba, .......}
L 1 = {comienza con a y termina con b } y L 2 = {comienza con b y termina con a}.
Entonces L= L 1 ∪ L 2 o L=L 1 + L 2
Diagrama de transición de estado para el lenguaje L 1 :
este DFA acepta todas las strings que comienzan con a y terminan con b. Aquí, el estado A es el estado inicial y el estado C es el estado final.
Diagrama de transición de estado para el lenguaje L 2 :
este DFA acepta todas las strings que comienzan con b y terminan con a. Aquí, el estado A es el estado inicial y el estado C es el estado final.
Ahora, Tomando la unión del lenguaje L 1 y L 2 que da el resultado final del lenguaje que comienza y termina con diferentes elementos.
Diagrama de transición de estado de L 1 ∪ L 2 :
Como vemos, L 1 y L 2 se han combinado a través del proceso de unión y este DFA final acepta todo el lenguaje que contiene strings que comienzan y terminan con símbolos diferentes.
Nota: Del ejemplo anterior también podemos inferir que los idiomas regulares están cerrados bajo unión (es decir, la unión de dos idiomas regulares también es regular).
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