Requisito previo: diseñar un autómata finito
Entendamos la intersección de dos DFA con un ejemplo.
Diseñar un DFA para el conjunto de strings sobre {0, 1} de modo que termine en 01 y tenga números pares 0f 1.
Allí se formarán dos idiomas deseados:
L1= {01, 001, 101, 0101, 1001, 1101, ....}
L2= {11, 011, 101, 110, 0011, 1100, .....}
L = L1 and L2 = L1 ∩ L2
Diagrama de transición de estado para el idioma L 1 :
este es un DFA para el idioma L 1
Acepta todas las strings que aceptan 01 al final.
Diagrama de transición de estado para el idioma L 2 :
Este es un DFA para el idioma L 2
Acepta toda la string que acepta con un número par de 1.
Diagrama de transición de estado de L 1 ∩ L 2 :
La intersección de L 1 y L 2 puede explicarse mediante un lenguaje que acepta una string sobre {0, 1} tal que termina en 01 y tiene un número par de 1.
L = L1 ∩ L2
= {1001, 0101, 01001, 10001, ....}
Por lo tanto, vemos que L 1 y L 2 se han combinado a través del proceso de intersección y este DFA final acepta todo el idioma que tiene un número par de 1 y termina en 01.
Publicación traducida automáticamente
Artículo escrito por _tanya_sri_ y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA