Necesita expresión regular para autómatas finitos: número par de 1 y número par de 0

Ya no necesitas investigar más en otros sitios ya que estás al sitio justo, contamos con la solución que buscas pero sin problemas.

Solución:

Cómo escribir expresiones regulares para un DFA usando el teorema de Arden

Permite en lugar de símbolos de lenguaje 0,1 nosotros tomamos Σ = a, b y lo que sigue es el nuevo DFA.

Observe que el estado de inicio es Q₀

No has dado pero en mi respuesta el estado inicial es Q₀, Donde el estado final también es Q₀.

El idioma aceptado por DFA es un conjunto de todas las cadenas que constan de un símbolo a y b donde número de símbolo a y b son pares (incluyendo Λ).

Algunas cadenas de ejemplo son Λ, aa, bb, abba, babbab , no hay restricción de orden y patrón de apariencia del símbolo, solo ambos deben ser un número par de tiempo.
Nota: Λ está permitido porque numberOf (a) y numberOf (b) es cero que es par.

Como dije en mi respuesta con líneas: Cómo escribir una expresión regular para un DFA, cada estado almacena cierta información. A continuación, se muestra qué información se almacena en cada estado en el DFA anterior.

Q₀: Número par de a e incluso un número de b

Q₁: Número impar de a e incluso un número de b

Q₂: Número impar de a y número impar de b

Q₃: Número par de a y número impar de b

(Puede crear DFA para idiomas más interesantes cambiando el conjunto de estados finales)
_{Uno debería leer la respuesta alineada, porque mi enfoque de la multa de RE para DFA en ambas respuestas es diferente}

¿Qué es una expresión regular?

El enfoque se explica a continuación utilizando el Teorema de Arden, aplicable en un diagrama de transición en el que hay un solo estado de inicio y no se define ningún movimiento nulo (nuestro DFA está en esta forma). La técnica se explica en un libro: Lenguajes formales y teoría de los autómatas.

Recuerde 4.2 TEOREMA DE ARDEN:

Dejar B y C son dos expresiones regulares sobre Σ. Si C no contiene Λ, entonces para la ecuación A = B + AC tiene una solución única (una y solo una) A = BC *.

[Solution]:

Paso 1: Escriba la ecuación inicial, una ecuación correspondiente a cada estado en DFA. Esta ecuación significa cómo se puede alcanzar un estado en un solo paso

Entonces, de acuerdo con nuestro DFA, las siguientes 4 ecuaciones son posibles:

1. Q₀ = Λ + Q₁a + Q₃B
2. Q₁ = Q₀a + Q₂B
3. Q₂ = Q₁b + Q₃a
4. Q₃ = Q₀b + Q₂a

En la ecuación (1) extra Λ es porque Q₀ es el estado inicial, se puede alcanzar sin ninguna entrada (un punto de inicio). Porque Q₀ también es solo un estado final, una cadena que consta de a, b es aceptable si termina en Q₀. Valor de Q₀ nos dará la expresión regular requerida por lo que nuestro objetivo es simplemente la ecuación- (1) en términos de a, b.

Paso 2: Simplifique la ecuación usando poniendo el valor de los estados de otras ecuaciones y usando la ecuación de simplificación de Arden.

Primero tomemos la ecuación- (4) y reemplacemos el valor de Q₂ de la ecuación- (3).

Q₃ = Q₀b + Q₂a
Q₃ = Q₀b + (Q₁b + Q₃a) un
Q₃ = Q₀b + Q₁ba + Q₃Automóvil club británico

La última ecuación se puede ver en forma de la ecuación de Arden A = B + AC. Donde A es Q₃, B = Q₀b + Q₁ba y C = aa. Entonces, de acuerdo con la termia de Arden, la ecuación Q₃ = Q₀b + Q₁ba + Q₃aa tiene una solución única que es:

Q₃ = (Q₀b + Q₁ba) (aa) *

O se puede escribir esto de la siguiente manera:

5. Q₃ = Q₀b (aa) * + Q₁ba (aa) *

Lógicamente, puede verificar / comprender eq- (5) significa Q₃ se puede llegar de dos maneras (+) puño de aplicando b en Q₀ luego hay un bucle con etiqueta aa en Q₃, la segunda forma es de Q₁ con aplicación de ba.

De manera similar, podemos simplificar la ecuación- (2)

Q₁ = Q₀a + Q₂B
Q₁ = Q₀a + (Q₁b + Q₃a) b
Q₁ = Q₀a + Q₁bb + Q₃ab

Utilice aquí las reglas de simplificación de Arden.

Q₁ = (Q₀a + Q₃ab) (bb) *

simplificar aún más

6. Q₁ = Q₀a (bb) * + Q₃ab (bb) *

Ahora valor de Q₃ de la ecuación- (5) a la ecuación- (6)

Q₁ = Q₀a (bb) * + (Q₀b (aa) * + Q₁ba (aa) *) ab (bb) *
Q₁ = Q₀a (bb) * + Q₀b (aa) * ab (bb) * + Q₁ba (aa) * ab (bb) *

Nuevamente mejore esta última ecuación utilizando la ley de simplificación de Arden.

Q₁ = (Q₀a (bb) * + Q₀b (aa) * ab (bb) *) (ba (aa) * ab (bb) *) *

tomar Q₀ estafador:

7. Q₁ = Q₀(a (bb) * + b (aa) * ab (bb) *) (ba (aa) * ab (bb) *) *

¿Puedes entender esta ecuación? Es cómo puedes ir a Q₁ del estado Q₀? Recordamos esta solución como ecuación- (7)

Como arriba podemos evaluar el valor de Q₁ en términos de estado Q₀ y a, bDe manera similar, debemos evaluar el valor para el estado Q₃. Para esto podemos poner simple valor del estado Q₁ de la ecuación- (5) a la ecuación- (7).

5. Q₃ = Q₀b (aa) * + Q₁ba (aa) *
. Q₃ = Q₀b (aa) * + Q₀(a (bb) * + b (aa) * ab (bb) *) (ba (aa) * ab (bb) *) * ba (aa) *
8. Q₃ = Q₀ (b (aa) * + (a (bb) * + b (aa) * ab (bb) *) (ba (aa) * ab (bb) *) * ba (aa) *)

Ahora, en la ecuación número (1) ponga el valor del estado Q₃ y Q₁ de la ecuación número (8) y (7) receptivamente.

Q₀ = Λ + Q₁a + Q₃B
Q₀ = Λ + Q₀(a (bb) * + (aa) * ab (bb) *) (ba (aa) * ab (bb) *) * a + Q₀ (b (aa) * + (a (bb) * + b (aa) * ab (bb) *) (ba (aa) * ab (bb) *) * ba (aa) *) b

Ahora, la última vez aplica la solución de Arden para encontrar el valor del estado Q₀ en términos de símbolos a y b.

Q₀ = Λ + ((a (bb) * + (aa) * ab (bb) *) (ba (aa) * ab (bb) *) * a + (b (aa) * + (a (bb) * + b ( aa) * ab (bb) *) (ba (aa) * ab (bb) *) * ba (aa) *) b) *

que es lo mismo que (podemos descartar Λ aquí) RE:

((a (bb) * + (aa) * ab (bb) *) (ba (aa) * ab (bb) *) * a + (b (aa) * + (a (bb) * + b (aa ) * ab (bb) *) (ba (aa) * ab (bb) *) * ba (aa) *) b) *

Este es el RE que estabas buscando.

No estoy seguro de que pueda simplificarse más. Te lo dejo como ejercicio.

En la pregunta vinculada, sugerí un método analítico y no formal, pero fue difícil de aplicar y encontrar RE para este DFA y esta pregunta demuestra el poder del teorema de Arden y la solución paso a paso.

Editar:

Mi expresión regular anterior es correcta pero difícil de asimilar debido a su forma asimétrica. A continuación, escribo una nueva forma de RE que es más simétrica.

Tenemos la ecuación- (5), (6) como sigue:

5. Q₃ = Q₀b (aa) * + Q₁ba (aa) *
6. Q₁ = Q₀a (bb) * + Q₃ab (bb) *

Ambos son de construcción simétrica y fáciles de aprender. (lea mi comentario después de la ecuación (5) anterior)

Para evaluar el valor del estado Q₁ en términos de Q₀, Puse el valor de Q₃ de la ecuación- (5) a la ecuación- (6) que me da la ecuación- (7) de la siguiente manera:

7. Q₁ = Q₀(a (bb) * + b (aa) * ab (bb) *) (ba (aa) * ab (bb) *) *

De manera similar, para evaluar el valor del estado Q₃ en términos de Q₀, podemos poner valor de Q₁ de la ecuación- (6) a la ecuación- (5) que nos dará una nueva forma de ecuación- (8) de la siguiente manera:

Q₃ = Q₀b (aa) * + Q₁ba (aa) *
Q₃ = Q₀b (aa) * + (Q₀a (bb) * + Q₃ab (bb) *) ba (aa) *
Q₃ = Q₀b (aa) * + Q₀a (bb) * ba (aa) * + Q₃ab (bb) * ba (aa) *

Ahora, podemos tener la ecuación- (8) en nuestra forma deseada:

8. Q₃ = Q₀(b (aa) * + a (bb) * ba (aa) *) (ab (bb) * ba (aa) *) *

Ahora, tenemos la ecuación- (1), (7), (8):

1. Q₀ = Λ + Q₁a + Q₃B
7. Q₁ = Q₀(a (bb) * + b (aa) * ab (bb) *) (ba (aa) * ab (bb) *) *
8. Q₃ = Q₀(b (aa) * + a (bb) * ba (aa) *) (ab (bb) * ba (aa) *) *

Ahora, podemos tener la ecuación- (8) en nuestra forma deseada:

8. Q₃ = Q₀(b (aa) * + a (bb) * ba (aa) *) (ab (bb) * ba (aa) *) *

Ahora, tenemos la ecuación- (1), (7), (8):

1. Q₀ = Λ + Q₁a + Q₃B
7. Q₁ = Q₀(a (bb) * + b (aa) * ab (bb) *) (ba (aa) * ab (bb) *) *
8. Q₃ = Q₀(b (aa) * + a (bb) * ba (aa) *) (ab (bb) * ba (aa) *) *

Ahora pon el valor del estado Q₁ y Q₃ en la ecuación- (1):

Q₀ = Λ + Q₀(a (bb) * + b (aa) * ab (bb) *) (ba (aa) * ab (bb) *) * a + Q₀(b (aa) * + a (bb) * ba (aa) *) (ab (bb) * ba (aa) *) * b

también se puede escribir como:

Q₀ = Λ + Q₀ ((a (bb) * + b (aa) * ab (bb) *) (ba (aa) * ab (bb) *) * a + (b (aa) * + a (bb) * ba (aa) *) (ab (bb) * ba (aa) *) * b)

A continuación, aplique el teorema de Arden en esta ecuación y obtenemos el RE final:

Expresión regular para números pares de ‘a’ e incluso números de ‘B’:

((a (bb) * + b (aa) * ab (bb) *) (ba (aa) * ab (bb) *) * a + (b (aa) * + a (bb) * ba (aa) *) (ab (bb) * ba (aa) *) * b) *

¿Se puede simplificar un paso más de la siguiente manera:

((a + b(aa)*ab)(bb)*(ba(aa)*ab(bb)*)*a + (b + a(bb)*ba)(aa)*(ab(bb)*ba(aa)*)*b)*

Nos puedes añadir valor a nuestra información participando con tu veteranía en las observaciones.

---

---

Utiliza Nuestro Buscador