Proceso de complementación en DFA – Part 1

Requisito previo: diseñar un autómata finito 
Supongamos que tenemos un DFA que está definido por ( Q,  \Sigma  \delta  , q0, F ) y acepta el lenguaje L 1 . Entonces, el DFA que acepta el lenguaje L 2 donde L 2 = ̅L 1 ‘, se definirá como sigue: 
 

( Q, \Sigma, \delta, q0, Q-F )

El complemento de un DFA se puede obtener haciendo que los estados no finales sean estados finales y viceversa . El idioma aceptado por el DFA L 2 complementado es el complemento del idioma L 1

Ejemplo-1: 
L 1 : conjunto de todas las strings sobre {a, b} de longitud uniforme 
 

L1 = {\epsilon, ab, aa, abaa, aaba, ....} 

L 2 : conjunto de todas las strings sobre {a, b} de longitud impar 
 

L2 = { a, b, aab, aaa, bba, bbb, ...} 

Aquí, podemos ver que L 2 = ̅L 1 

Primero dibujemos el DFA para L 1 que acepta las strings de longitud uniforme. 

Ahora, para diseñar el DFA para L 2 , solo necesitamos complementar el DFA anterior. Cambiaremos los estados no finales por estados finales y los estados finales por estados no finales. 

Este es nuestro DFA complementado requerido. 

Ejemplo-2: 
L 1 : conjunto de todas las strings sobre {a, b} que comienzan con ‘a’. 
 

L1 ={ a, ab, aa, aba, aaa, aab, ..} 

L 2 : conjunto de todas las strings sobre {a, b} que no comienzan con ‘a’. 
 

L2 ={ \epsilon, b, ba, bb, bab, baa, bba, ...} 

Aquí, podemos ver que L 2 = ̅L 1 

Primero dibujemos el DFA para L 1 que acepta el conjunto de todas las strings sobre {a, b} comenzando con ‘a’ 

Ahora, para diseñar el DFA para L 2 , solo necesitamos complementar el DFA anterior. Cambiaremos los estados no finales por estados finales y los estados finales por estados no finales. 

Este es nuestro DFA complementado requerido que acepta las strings que no comienzan con ‘a’. 
Nota: Los lenguajes regulares están cerrados bajo el complemento (es decir, el complemento del lenguaje regular también será regular).
 

Publicación traducida automáticamente

Artículo escrito por SUDIPTADANDAPAT 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 *