En la teoría del lenguaje formal y la coincidencia de patrones , la alternancia es la unión de dos conjuntos de cadenas o, equivalentemente, la disyunción lógica de dos patrones que describen conjuntos de cadenas.
Los lenguajes regulares están cerrados bajo alternancia, lo que significa que la alternancia de dos lenguajes regulares es nuevamente regular. [1] En las implementaciones de expresiones regulares , la alternancia a menudo se expresa con una barra vertical que conecta las expresiones para los dos lenguajes cuya unión se va a hacer coincidir, [2] [3] mientras que en estudios más teóricos se puede usar el signo más para este propósito. [1] La capacidad de construir autómatas finitos para uniones de dos lenguajes regulares que están definidos por autómatas finitos es central para la equivalencia entre lenguajes regulares definidos por autómatas y por expresiones regulares. [4]
Otras clases de lenguajes que están cerrados bajo la alternancia incluyen lenguajes libres de contexto y lenguajes recursivos . La notación de barra vertical para la alternancia se utiliza en el lenguaje SNOBOL y algunos otros lenguajes. En la teoría del lenguaje formal, la alternancia es conmutativa y asociativa . Esto no es en general cierto para la forma de alternancia utilizada en lenguajes de coincidencia de patrones, debido a los efectos secundarios de realizar una coincidencia en esos lenguajes.