Alternancia (teoría del lenguaje formal)
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.
Referencias
- ^ ab Linz, Peter (2006). "Teorema 4.1". Introducción a los lenguajes formales y autómatas . Jones & Bartlett Learning. págs. 100-101. ISBN 9780763737986.
- ^ Fitzgerald, Michael (2012). "Alternancia". Introducción a las expresiones regulares: desentrañamiento de las expresiones regulares, paso a paso . O'Reilly Media. pp. 43–45. ISBN 9781449338893.
- ^ "Alternancia con la barra vertical". regular-expressions.info . Consultado el 11 de noviembre de 2021 .
- ^ Cooper, Keith; Torczon, Linda (2011). Ingeniería de un compilador (2.ª ed.). Elsevier. pág. 41. ISBN 9780080916613.
Bibliografía
- John E. Hopcroft y Jeffrey D. Ullman, Introducción a la teoría de autómatas, lenguajes y computación , Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X .
.svg/1280px-Encoder_Disc_(3-Bit).svg.png) | Este artículo relacionado con la combinatoria es un esbozo . Puedes ayudar a Wikipedia expandiéndolo. |
.svg){kind=link}
