En informática teórica , la regla de Arden , también conocida como lema de Arden , es una declaración matemática sobre una determinada forma de ecuaciones del lenguaje .
Fondo
Un lenguaje (formal) es simplemente un conjunto de cadenas. Estos conjuntos pueden especificarse mediante alguna ecuación de lenguaje , que a su vez se basa en operaciones sobre lenguajes. Las ecuaciones de lenguaje son enunciados matemáticos que se asemejan a ecuaciones numéricas, pero las variables asumen valores de lenguajes formales en lugar de números. Entre las operaciones más comunes en la mayoría de los dos idiomas A y B son la unión de conjuntos A ∪ B , y su concatenación Un ⋅ B . Por último, como una operación de tomar un solo operando , el conjunto A * denota la estrella de Kleene de la lengua A .
Declaración de la regla de Arden
La regla de Arden establece que el conjunto A * ⋅ B es el lenguaje más pequeño que es una solución para X en la ecuación lineal X = A ⋅ X ∪ B donde X , A , B son conjuntos de cadenas. Además, si el conjunto A no contiene la palabra vacía, esta solución es única. [1] [2]
De manera equivalente, el conjunto B ⋅ A * es el idioma más pequeño que es una solución para X en X = X ⋅ A ∪ B .
Solicitud
La regla de Arden se puede utilizar para ayudar a convertir algunos autómatas finitos en expresiones regulares, como en el algoritmo de Kleene .
Ver también
Notas
- ^ Daintith, John (2004). "Regla de Arden" . Archivado desde el original el 13 de febrero de 2010 . Consultado el 10 de marzo de 2010 .
- ^ Sutner, Klaus. "Álgebra de lenguajes regulares" (PDF) . Archivado desde el original (PDF) en 2011-07-08 . Consultado el 15 de febrero de 2011 .
Referencias
- Arden, DN (1960). Lógica retardada y máquinas de estados finitos, Teoría del diseño de máquinas informáticas , págs. 1-35, University of Michigan Press, Ann Arbor, Michigan, EE. UU.
- Dean N. Arden (octubre de 1961). "Máquinas de estado finito y lógica retardada" . Proc. 2nd Ann. Symp. sobre teoría de circuitos de conmutación y diseño lógico (SWCT), Detroit / MI . (resumen de acceso abierto)
- John E. Hopcroft y Jeffrey D. Ullman, Introducción a la teoría, los lenguajes y la computación de los autómatas , Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X . Capítulo 2: Autómatas finitos y expresiones regulares, p.54.
- Arden, DN Introducción a la teoría de las máquinas de estados finitos , Monografía No. 12, Proyecto de conceptos de sistemas discretos, 28 de junio de 1965.