Encontrar el complemento de un DFA?

Se me pide que muestre el diagtwig de DFA y RegEx para el complemento de RegEx (00 + 1)* . En el problema anterior tuve que demostrar que el complemento de un DFA está cerrado y también es una expresión regular, así que sé que para convertir un DFA, M al complemento, M`, solo necesito cambiar los estados iniciales de aceptación y estados finales de aceptación.

Sin embargo, parece que los estados iniciales de aceptación para el RegEx son {00, 1, ^} y los estados finales de aceptación son {00, 1, ^} también. Así que intercambiarlos resultará exactamente en el mismo RegEx y DFA que parece contradictorio.

¿Estoy haciendo algo mal o se supone que este RegEx no tiene un complemento real?

Gracias

Como dices en pregunta:

Sé que para convertir un DFA, M al complemento, M`, solo necesito cambiar los estados iniciales de aceptación y los estados finales de aceptación.

No es un complemento , pero estás haciendo algo así como el reverso de un idioma y los lenguajes regulares son el cierre en reversa .

Inversión de DFA

¿Cuál es el lenguaje de reversión?

La reversión de un lenguaje L (denotado L R ) es el lenguaje que consiste en la inversión de todas las cadenas en L.

Dado que L es L (A) para algunos FA A, podemos construir un autómata para L R :

  • revertir todos los bordes (arcos) en el diagtwig de transición

  • el estado de aceptación para el autómata L R es el estado de inicio para A

  • crear un nuevo estado de inicio para el nuevo autómata con transiciones epsilon a cada uno de los estados de aceptación para A

Nota : Al invertir todas sus flechas e intercambiar los roles de los estados iniciales y de aceptación de un DFA, puede obtener un NFA en su lugar.
es por eso que escribí FA (no DFA)

Complemento de DFA

Encontrar el complemento de un DFA?

Defination: el complemento de un idioma se define en términos de la diferencia establecida entre Σ * (estrella sigma). eso es L = Σ * – L.

Y el lenguaje de complemento (L ) de L tiene todas las cadenas de Σ * (sigma star) excepto las cadenas en L. Σ * son todas las cadenas posibles sobre el alfabeto Σ.
Σ = Conjunto de símbolos de idioma

Para construir el DFA D que acepta el complemento de L, simplemente convierta cada estado de aceptación en A en un estado no aceptante en D y convierta cada estado no aceptante en A en un estado de aceptación en D.
( ¡Advertencia! Esto no es verdad para NFA )

A es DFA de L, D es para complemento

Nota : Para construir DFA de complemento, DFA antiguo debe ser un medio completo, debe existir toda la posible ventaja de cada estado (o en otras palabras, δ debe ser una función completa ).

Complemento: referencia con el ejemplo

Complemento DFA para expresión regular (00+1)*

a continuación, DFA se llama A :

00 + 1

Pero no este DFA no es un DFA completo. la función de transición δ está parcialmente definida, pero no para el dominio completo Q×Σ ( falta el borde de salida de q1 para la etiqueta 1 ).

Su DFA completo puede ser el siguiente ( A ):

completeDFA

En el DFA anterior, se definen todas las transacciones posibles (* para cada par de Q,Σ *) y δ es una función completa en este caso.

Reff: para aprender qué es la función parcial.

El nuevo complemento DFA D se puede construir cambiando todos los estados finales q0 a estados no finales y viceversa.

Entonces, en el complemento q0 convierte en no final y q1, q2 son los estados finales.

complemento

Ahora puede escribir expresiones regulares para el lenguaje complementario usando ARDEN’S THEOREM y DFA I given.

Aquí escribo Expresión regular para complemento directamente:

(00 + 1)* 0 (^ + 1(1 + 0)*)

donde ^ es el símbolo nulo.

algunos enlaces útiles :
Desde aquí y a través de mi perfil, puedes encontrar algunas respuestas más útiles en FA. Además, dos buenos enlaces en las propiedades del lenguaje regular: uno , segundo

No me tomé el tiempo para leer toda la respuesta de Grijesh, pero esta es la manera más sencilla de obtener un DFA que acepte el complemento de un idioma, dado que un DFA acepta el idioma: use el mismo DFA, pero cambie los estados aceptables para que no acepte , y viceversa.

Las cadenas previamente aceptadas serán rechazadas, y las cadenas previamente rechazadas serán aceptadas. Dado que todas las transiciones se deben definir en cualquier DFA válido, y dado que todas las cadenas de entrada conducen exactamente a un estado, esto siempre funciona.

Para obtener un DFA para la reversión, primero puede construir un NFA agregando un nuevo estado inicial que se ramifique de manera no determinista a todos los estados de aceptación del DFA original. Invierta todas las transiciones del DFA original y haga que el único estado de aceptación sea el estado inicial del DFA original.