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 .
Un lenguaje (formal) es simplemente un conjunto de cadenas. Dichos conjuntos se pueden especificar por medio de 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 parecen a ecuaciones numéricas, pero las variables asumen valores de lenguajes formales en lugar de números. Entre las operaciones más comunes sobre dos lenguajes A y B están la unión de conjuntos A ∪ B y su concatenación A ⋅ B . Finalmente, como una operación que toma un solo operando , el conjunto A * denota la estrella de Kleene del lenguaje A .
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, entonces esta solución es única. [1] [2]
Equivalentemente, el conjunto B ⋅ A * es el lenguaje más pequeño que es una solución para X en X = X ⋅ A ∪ B .
La regla de Arden se puede utilizar para ayudar a convertir algunos autómatas finitos en expresiones regulares, como en el algoritmo de Kleene .