 |
| Figura 1.16 |
En la Figura anterior B y C son equivalentes, porque al unirlos no cambia su configuración en la aceptación o rechazo de palabras, o sea, los dos estados tienen la misma condición de aceptación (son finales) y su alfabeto de entrada es el mismo (d).
Cuando dos estados son equivalentes, se elimina uno para evitar redundancias. El problema de esta acción radica en qué hacer con las flechas que conectan el estado eliminado con el resto. Esto se soluciona con los siguientes criterios (4):
- Las flechas que salen del estado eliminado son eliminadas.
- Las flechas que llegan al estado eliminado son redirigidas hacia su estado equivalente.
Construir Tabla: Las filas y columnas están etiquetadas con estados. Representando una pareja de estados del autómata. Ejemplo: Del AFD (Figura 1.16) su Tabla de estados equivalentes es:
A
|
simétrico
|
simétrico
|
||
B
|
simétrico
|
|||
C
|
||||
A
|
B
|
C
|
||
Esta tabla se construye de forma optimizada, o sea, triangular porque se buscan relaciones de equivalencia:
B
|
|||
C
|
|||
A
|
B
|
||
Marcar estados distinguibles en la tabla: Se realiza un recorrido de izquierda a derecha y cada columna de arriba a abajo. En este caso los pares distinguibles son (A, B) y (A, C). Siendo el par (B, C) posibles equivalentes.
B
|
X
|
||
C
|
X
|
||
A
|
B
|
||
Analizar posibles estados equivalentes: Para analizar si los estados son equivalentes, se utilizan sus alfabetos de entrada. En este caso sería (d).
Si se analiza el par (B, C), a la vez se analiza (C, B) porque se cumple la propiedad simétrica de una relación binaria de equivalencia.
δ(B, d) = C , δ(C, d) = C se forma el par (C, C). Al analizar este par equivalente se halla en la diagonal. Si el par formado en la tabla se encuentra marcado entonces no es equivalente y se marca, de lo contrario, es equivalente.
B
|
X
|
||
C
|
X
|
(B, C)
|
|
A
|
B
|
||
Al terminar el recorrido, los estados equivalentes se unen, teniendo en cuenta los criterios mencionados.
B
|
(B, C)
|
||
C
|
X
|
||
A
|
B
|
||
Si se analiza la casilla (B, C) y no son equivalentes, la casilla (A, B) se marca como no equivalente porque contiene a este par
B
|
√
|
||
C
|
X
|
√
|
|
A
|
B
|
||
Se construye la tabla y se marcan los distinguibles
q2
|
X
|
||||||
q3
|
X
|
||||||
q4
|
X
|
X
|
|||||
q5
|
X
|
X
|
|||||
q6
|
X
|
X
|
X
|
||||
q7
|
X
|
X
|
X
|
||||
q1
|
q2
|
q3
|
q4
|
q5
|
q6
|
||
Al analizar la casilla (q1, q4): los alfabetos de entrada son {a, b, c, d}, como para cada cadena de entrada x, δ(q1, x) ≡ δ (q4, x), y se elabora latabla de transición de equivalencia
a
|
d
|
c
|
d
|
|
q1
|
q4
|
q5
|
q2
|
q3
|
q4
|
q6
|
Tabla de transición de equivalencia: Forma de representar δ(q, x) ≡ δ (p, x) siendo (x) una cadena de entrada. Las intersecciones de fila y columna muestran el próximo estado con la cadena de entrada específica. Si contiene la tabla una casilla vacía, los estados q y p no son equivalentes. Pero cuando todas las casillas se marcan, o sea, están ocupadas, los pares que se forman son responden a la unión del superior con el inferior. Ejemplo: (q4,q6). Como los estados q1 y q4 no son equivalentes, se marca la casilla
q2
|
X
|
||||||
q3
|
X
|
||||||
q4
|
√
|
X
|
X
|
||||
q5
|
X
|
X
|
|||||
q6
|
X
|
X
|
X
|
||||
q7
|
X
|
X
|
X
|
||||
q1
|
q2
|
q3
|
q4
|
q5
|
q6
|
||
Al analizar la casilla (q1, q5): los alfabetos de entrada son {a, b, c, d}, como para cada cadena de entrada x,δ(q1, x) ≡ δ (q5, x), elaborándose lasiguiente tabla de transición de equivalencia.
a
|
d
|
c
|
d
|
|
q1
|
q4
|
q5
|
q2
|
q3
|
q5
|
q7
|
Como los estados q1 y q5 no son equivalentes, se marca la casilla
q2
|
X
|
||||||
q3
|
X
|
||||||
q4
|
√
|
X
|
X
|
||||
q5
|
√
|
X
|
X
|
||||
q6
|
X
|
X
|
X
|
||||
q7
|
X
|
X
|
X
|
||||
q1
|
q2
|
q3
|
q4
|
q5
|
q6
|
Al analizar la casilla (q2, q3): elalfabeto de entrada es {c}, como para cada cadena de entrada x,δ(q2, x) ≡ δ (q3, x), se elabora la tabla de transición de equivalencia
c
|
|
q2
|
q2
|
q3
|
Los estados q2 y q3 no son equivalentes, se marca la casilla
q2
|
X
|
||||||
q3
|
X
|
√
|
|||||
q4
|
√
|
X
|
X
|
||||
q5
|
√
|
X
|
X
|
||||
q6
|
X
|
X
|
X
|
||||
q7
|
X
|
X
|
X
|
||||
q1
|
q2
|
q3
|
q4
|
q5
|
q6
|
Al analizar la casilla (q2, q6): el alfabeto de entrada es{c}, como para cada cadena de entrada x,δ(q2, x) ≡ δ (q6, x), y se elabora la tabla de transición de equivalencia
c
|
|
q2
|
q2
|
q6
|
q6
|
El par formado (q2, q6), no se encuentra marcada la casilla. Por ende, los estados q2 y q6 son equivalentes, y se marca la casilla
q2
|
X
|
||||||
q3
|
X
|
√
|
|||||
q4
|
√
|
X
|
X
|
||||
q5
|
√
|
X
|
X
|
||||
q6
|
X
|
(q2, q6)
|
X
|
X
|
|||
q7
|
X
|
X
|
X
|
||||
q1
|
q2
|
q3
|
q4
|
q5
|
q6
|
Al analizar la casilla (q2, q7): el alfabeto de entrada es{c}, como para cada cadena de entrada x,δ(q2, x) ≡ δ (q7, x) y se elabora la tabla de transición de equivalencia
c
|
|
q2
|
q2
|
q7
|
Los estados q2 y q7 no son equivalentes, por lo que se marca la casilla
q2
|
X
|
||||||
q3
|
X
|
√
|
|||||
q4
|
√
|
X
|
X
|
||||
q5
|
√
|
X
|
X
|
||||
q6
|
X
|
(q2, q6)
|
X
|
X
|
|||
q7
|
X
|
√
|
X
|
X
|
|||
q1
|
q2
|
q3
|
q4
|
q5
|
q6
|
Al analizar la casilla (q3, q6): el alfabeto de entrada es {c}, como para cada cadena de entrada x,δ(q3, x) ≡ δ (q6, x)y se elabora la tabla de transición de equivalencia
c
|
|
q3
|
|
q6
|
q6
|
Los estados q3 y q6 no son equivalentes, de ahí que se marque la casilla
q2
|
X
|
||||||
q3
|
X
|
√
|
|||||
q4
|
√
|
X
|
X
|
||||
q5
|
√
|
X
|
X
|
||||
q6
|
X
|
(q2, q6)
|
√
|
X
|
X
|
||
q7
|
X
|
√
|
X
|
X
|
|||
q1
|
q2
|
q3
|
q4
|
q5
|
q6
|
Al analizar la casilla (q3, q7): no contienen alfabetos de entrada. En este caso los dos estados tienen la condición de aceptación. Se marcan como equivalentes
q2
|
X
|
||||||
q3
|
X
|
√
|
|||||
q4
|
√
|
X
|
X
|
||||
q5
|
√
|
X
|
X
|
||||
q6
|
X
|
(q2, q6)
|
√
|
X
|
X
|
||
q7
|
X
|
√
|
(q3, q7)
|
X
|
X
|
||
q1
|
q2
|
q3
|
q4
|
q5
|
q6
|
Al analizar la casilla (q4, q5): el alfabeto de entrada es {a}, como para cada cadena de entrada x,δ(q4, x) ≡ δ (q5, x) y se elabora la tabla de transición de equivalencia
a
|
|
q4
|
q6
|
q5
|
q7
|
Al analizar los siguientes pares: Si se revisa en la tabla el par (q6, q7)no se encuentra la casilla marcada, por tanto q4 y q5 son equivalentes
q2
|
X
|
||||||
q3
|
X
|
√
|
|||||
q4
|
√
|
X
|
X
|
||||
q5
|
√
|
X
|
X
|
(q6, q7)
|
|||
q6
|
X
|
(q2, q6)
|
√
|
X
|
X
|
||
q7
|
X
|
√
|
(q3, q7)
|
X
|
X
|
||
q1
|
q2
|
q3
|
q4
|
q5
|
q6
|
Al analizar la casilla (q6, q7): el alfabeto de entrada es {c}, como para cada cadena de entrada x,δ(q6, x) ≡ δ (q7, x). y se elabora la tabla de transición de equivalencia
c
|
|
q6
|
q6
|
q7
|
Los estados q6 y q7 no son equivalentes, si se observa en la tabla, en la casilla (q4, q5) se encuentra el par (q6, q7)por ende q4 y q5 no son equivalentesyse marca la casilla
q2
|
X
|
||||||
q3
|
X
|
√
|
|||||
q4
|
√
|
X
|
X
|
||||
q5
|
√
|
X
|
X
|
√
|
|||
q6
|
X
|
(q2, q6)
|
√
|
X
|
X
|
||
q7
|
X
|
√
|
(q3, q7)
|
X
|
X
|
√
|
|
q1
|
q2
|
q3
|
q4
|
q5
|
q6
|
Los estados equivalentes son: q2 ≡ q6, q3 ≡ q7, siendo el autómata finito determinista optimizado
Recomendacion: Leer:
Expresiones regulares a partir del autómata finito equivalente: Parte I
Expresiones regulares a partir del autómata finito equivalente: Parte II
Algoritmo de conversión de expresión regular a aut...
Algoritmo de conversión de Autómata finito no determinista a un Autómata finito determinista
Referencias Bibliográficas
1. Pérez Martínez, Abel. ERAFPLN. 2009.
2. PÉREZ, NALLY CAMPO. INTRODUCCIÓN A LA TEORÍA DE CONJUNTOS. [En
línea] http://www.e-socrates.org/mod/resource/view.php?id=4398.
3. REAL ACADEMIA ESPAÑOLA. [En línea] http://buscon.rae.es/draeI/.
4. Brena, Ramón. AUTOMATAS Y LENGUAJES. Monterrey : s.n., 2003.
5. Hopcroft, John E. Introducion to automata theory, languages, and computation.
s.l. : Addison-Wesley, 2001.
6. Lawson, M. V. Finite automata.
http://www.ma.hw.ac.uk/~markl/preprints/Lawson.pdf. [En línea]
7. RegExlib. [En línea] http://regexlib.com/default.aspx.
8. Javascript Regular Expression Validator. [En línea]
http://tools.netshiftmedia.com/regexlibrary/.
9. RegexPal. [En línea] http://regexpal.com/.
10. metriplica.com, Grupo. ¡Prueba tus Expresiones Regulares!
http://www.metriplica.com/4_4_herramientas.asp. 2008.
11. Regular Expression Tool. [En línea]
http://erik.eae.net/playground/regexp/regexp.html.
12. Regexp Editor. [En línea] http://myregexp.com/.
13. Rad Software Regular Expression Designer 1.4.7528.27091. [En línea]
http://www.radsoftware.com.au/?from=RegexDesigner.
14. Visual REGEXP 3,0. [En línea] http://www.softpedia.com/get/Programming/OtherProgramming-Files/Visual-REGEXP.shtml.
15. Regulazy v1.0.3.0 (Beta). [En línea] http://tools.osherove.com/Default.aspx.
16. Regular Expression Workbench. [En línea] EricGu@Microsoft.Com.
17. Sells, Chris and Weinhardt, Michael. RegexDesigner v1.0.2727. [En línea]
http://www.sellsbrothers.com/tools/.
18. Visual Automata Simulator. [En línea] http://www.cs.usfca.edu/~jbovet/.
19. Acosta, Francisco Ríos. SP-PS1. [En línea] http://www.friosa.com.mx.
20. RegexBuddy3. [En línea] http://www.regexbuddy.com/.
21. The Software Process Dashboard Initiative. [En línea]
http://www.processdash.com/.
22. METODOLOGÍA DE MUESTREO. [En línea]
http://www.hsa.es/id/investigacion/uai/uai_docs/muestreo/muestreo.htm.
23. Modelos Abstractos de Cómputo I. [En línea]
http://www.sc.ehu.es/jiwnagom/MAC1/MAC-archivos/Tema2-parte3.pdf.
