En la teoría del lenguaje formal , el teorema de representación de Chomsky-Schützenberger es un teorema derivado por Noam Chomsky y Marcel-Paul Schützenberger sobre la representación de un lenguaje libre de contexto dado en términos de dos lenguajes más simples. Estos dos lenguajes más simples, a saber, un lenguaje regular y un lenguaje Dyck , se combinan mediante una intersección y un homomorfismo .
Algunas nociones de la teoría del lenguaje formal están en orden. Un lenguaje libre de contexto es regular , si puede describirse mediante una expresión regular o, de manera equivalente, si es aceptado por un autómata finito . Un homomorfismo se basa en una función que mapea símbolos de un alfabeto a palabras sobre otro alfabeto ; Si el dominio de esta función se extiende a palabras sobre de forma natural, dejando por todas las palabras y , esto produce un homomorfismo . Un alfabeto combinado es un alfabeto con dos conjuntos de igual tamaño; conviene pensarlo como un conjunto de tipos de paréntesis, donde contiene los símbolos del paréntesis de apertura, mientras que los símbolos en contiene los símbolos de paréntesis de cierre. Para un alfabeto coincidente, el idioma Dyck es dado por
palabras que están bien anidadas entre paréntesis .
- Teorema de Chomsky-Schützenberger . Una lengua L sobre el alfabeto. es libre de contexto si y solo si existe
- un alfabeto combinado
- un idioma regular encima ,
- y un homomorfismo
- tal que .
Las pruebas de este teorema se encuentran en varios libros de texto, por ejemplo, Autebert, Berstel y Boasson (1997) o Davis, Sigal y Weyuker (1994) .
Referencias
- Autebert, Jean-Michel; Berstel, Jean; Boasson, Luc (1997). "Lenguajes libres de contexto y autómatas pushdown" (PDF) .En G. Rozenberg y A. Salomaa, eds., Handbook of Formal Languages, vol. 1: Palabra, lenguaje, gramática (págs. 111-174). Berlín: Springer-Verlag . ISBN 3-540-60420-0.
- Davis, Martin D .; Sigal, Ron; Weyuker, Elaine J. (1994). Computabilidad, complejidad y lenguajes: fundamentos de la informática teórica (2ª ed.). Ciencia de Elsevier. pag. 306. ISBN 0-12-206382-1.