NO BORRAR

2. Las construcciones de Dn
Esta sección proporciona algunos valores para Dn mediante el análisis de varias clases de lenguajes regulares. En la descripción de la función de transición de nuestraDFA y -DFAs, todas las transiciones conducen al estado de error (un estado no final fregadero) a menos que se indique lo contrario. Además, en nuestras cifras, el estado de error y las transiciones queconducen a él han sido retirados para mayor claridad. A menudo nos referiremos a la siguiente algoritmo.

Dado un -DFA = (Q ?, Σ ?, δ ?, q 0, M??) M y una -substitution σ, Algorithm1 da una DFA mínimoque acepta σ (L (M)?)???:
• Construir un NFA N = (Q ?, Σ, δ, q? 0, F?) Que acepta σ (L (M?)), Donde δ (q, a) = {δ? (Q, a)} si un ∈Σ \ σ (?) y δ (q, a) = {δ? (q, a), δ? (q,?)} si un ∈σ (?).
•Convertir N a un mínimo de DFA equivalente.
2.1. Idiomas de las palabras de la misma longitud
En primer lugar, nos fijamos en los idiomas de las palabras de la misma longitud. Le damos tres construcciones.Nuestro primer constructo se ilustra en la Fig.1.
Teorema 1. Para n ≥1,? N-13 2+? N-13 2 + (n-1) mod3 ∈Dn.
Proof.Let d =? N-13 yr = (n-1) mod3. Definimos la DFA M = (Q, Σ, δ, q0, F) como sigue:

Q ={(0, 0)} ∪Q1∪Q2∪Q3, donde q0 = (0, 0), Q1 = {(1, i) | 0 ≤i • Σ = {a0, ..., ad-1} ∪{b1, ..., bd-1} ∪ {bd + 1, ..., b2d-1} ∪ {c};


Fig.1.DFAM (izquierda) y? -DFAM? (Derecha) de Theorem1, n = 11. Los estados de error se omiten.


Fig.2.DFAM (izquierda) y? -DFAM? (Derecha) del teorema 2,n = 11, los estados de error x = 4.Los se omiten.

δis define como sigue:
-δ ((0,0), ai) = (1, i) para todos ai∈Σ,
-δ ((1, i), aj) = (2, ID + j) si (1, i), (2, ID + j) ∈Qand aj∈Σ,
-δ ((2, i), bj) =(3, 0) si (2, i) ∈Q, bj∈Σ, j =? id o j = (i Modd) + d,
-δ ((i, 0), c) = (i 1, 0) para 3 ≤i ≤2 + r.
Observe que L = L (M) = {aiajbkcr | ai, aj, bk∈Σ; k = iork = d + j} y que Mcontains | Q1 | + | Q2 |...

Leer documento completo

Regístrate para leer el documento completo.