En este artículo diseñaremos los Autómatas Finitos Deterministas del Lenguaje Regular L ={w ∈ {a, b}* : Na(w) mod 3 > Nb(w) mod 3}.
La expresión regular puede ser cualquier cosa, desde un símbolo terminal, ∅, hasta la unión de dos expresiones regulares (R1 + R2), su intersección (R1 + R2) o el cierre de la expresión regular (R1*) o un ∈ Σ, donde Σ es el finito conjunto de símbolos de entrada, que también es una expresión regular del lenguaje {a}.
El lenguaje regular es un lenguaje que se puede expresar en términos de expresión regular.
Ejemplos de expresiones regulares:
- Expresión regular del conjunto de todas las strings Σ = {a, b} con exactamente una a.
b*ab*
- Expresión regular del conjunto de todas las strings Σ = {a, b} que comienzan con el prefijo ab.
ab(a+b)*
Problema:
Lenguaje regular L = {w ∈ {a, b}* : Na(w) mod 3 > Nb(w) mod 3} significa que el lenguaje acepta todas las strings donde el conteo de a en el módulo de string 3 es mayor que el cuenta del módulo 3 de b.
Ejemplos:
Input : aaabbbb Output : Not Accepted Reason : Na(w) = 3; 3 mod 3 = 0 and Nb(w) = 4; 4 mod 3 = 1. So Na(w) mod 3 !> Nb(w) mod 3 Input : aabbbb Output : Accepted Reason : Na(w) = 2 and Nb(w) = 4; 2 mod 3 = 2 and 4 mod 3 = 1. So Na(w) mod 3 > Nb(w) mod 3
Enfoque:
Dado que es el módulo 3, los residuos pueden ser 0, 1, 2.
Cuando Na(w) mod 3 = 0, cualquiera que sea el valor de Nb(w) mod 3, no se aceptará el idioma.
Cuando Na(w) mod 3 = 1, entonces el idioma se acepta cuando Nb(w) mod 3 = 0.
Nuevamente, cuando Na(w) mod 3 = 2, entonces el idioma se acepta cuando Nb(w) mod 3 = 0 o 1.
Esto se puede explicar en forma tabular:
| a | b | PRODUCCIÓN |
|---|---|---|
|
0 |
0 |
NO ACEPTADA |
|
0 |
1 |
NO ACEPTADA |
|
0 |
2 |
NO ACEPTADA |
|
1 |
0 |
ACEPTADO |
|
1 |
1 |
NO ACEPTADA |
|
1 |
2 |
NO ACEPTADA |
|
2 |
0 |
ACEPTADO |
|
2 |
1 |
ACEPTADO |
|
2 |
2 |
NO ACEPTADA |
Entonces, los estados q10, q20 y q21 serán los estados finales donde se aceptará el lenguaje.
El diagrama final de transición de estado de DFA será:
Publicación traducida automáticamente
Artículo escrito por srishtiganguly1999 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA