En la teoría del lenguaje formal y la coincidencia de patrones , la alternancia es la unión de dos conjuntos de cadenas o, de manera equivalente, 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 vuelve a ser regular. [1] En implementaciones de expresiones regulares , la alternancia a menudo se expresa con una barra vertical que conecta las expresiones de los dos idiomas cuya unión debe coincidir, [2] [3] mientras que en estudios más teóricos el signo más puede usarse para este propósito. [1] La capacidad de construir autómatas finitos para uniones de dos lenguajes regulares que a su vez están definidos por autómatas finitos es fundamental para la equivalencia entre lenguajes regulares definidos por autómatas y por expresiones regulares. [4]
Otras clases de lenguajes que están cerrados bajo alternancia incluyen lenguajes libres de contexto y lenguajes recursivos . La notación de barra vertical para alternancia se utiliza en el idioma SNOBOL y en algunos otros idiomas. En la teoría del lenguaje formal, la alternancia es conmutativa y asociativa . En general, esto no es cierto para la forma de alternancia utilizada en los lenguajes de coincidencia de patrones, debido a los efectos secundarios de realizar una coincidencia en esos idiomas.