Teorema de representación de Chomsky-Schützenberger

En 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 en 1959 ^[1] 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 por medio de una intersección y un homomorfismo .

Las demostraciones de este teorema se encuentran en varios libros de texto, por ejemplo, Autebert, Berstel y Boasson (1997) o Davis, Sigal y Weyuker (1994).

Matemáticas

Notación

Conviene recordar algunas nociones de la teoría del lenguaje formal.

Un lenguaje libre de contexto es regular si puede describirse mediante una expresión regular o, equivalentemente, si es aceptado por un autómata finito .

Un homomorfismo se basa en una función que asigna símbolos de un alfabeto a palabras de otro alfabeto ; si el dominio de esta función se extiende a palabras de la forma natural, dejando para todas las palabras y , esto produce un homomorfismo . ${\displaystyle h}$ ${\displaystyle \Gamma }$ ${\displaystyle \Sigma }$ ${\displaystyle \Gamma }$ ${\displaystyle h(xy)=h(x)h(y)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle h:\Gamma ^{*}\to \Sigma ^{*}}$

Un alfabeto emparejado es un alfabeto con dos conjuntos de igual tamaño; es conveniente pensar en él como un conjunto de tipos de paréntesis, donde contiene los símbolos de paréntesis de apertura, mientras que los símbolos en contienen los símbolos de paréntesis de cierre. Para un alfabeto emparejado , el lenguaje Dyck tipado viene dado por ${\displaystyle T\cup {\overline {T}}}$ ${\displaystyle T}$ ${\displaystyle {\overline {T}}}$ ${\displaystyle T\cup {\overline {T}}}$ ${\displaystyle D_{T}}$

${\displaystyle D_{T}=\{\,w\in (T\cup {\overline {T}})^{*}\mid w{\text{ is a correctly nested sequence of parentheses}}\,\}.}$

Por ejemplo, la siguiente es una oración válida en el lenguaje Dyck de tres tipos:

( [ [ ] { } ] ( ) { ( ) } )

Teorema

Un idioma L sobre el alfabeto es libre de contexto si y sólo si existe ${\displaystyle \Sigma }$

• un alfabeto emparejado ${\displaystyle T\cup {\overline {T}}}$
• un lenguaje regular sobre , ${\displaystyle R}$ ${\displaystyle T\cup {\overline {T}}}$
• y un homomorfismo ${\displaystyle h:(T\cup {\overline {T}})^{*}\to \Sigma ^{*}}$

de tal manera que . ${\displaystyle L=h(D_{T}\cap R)}$

Podemos interpretar esto como que cualquier lenguaje CFG puede generarse generando primero un lenguaje Dyck tipado, filtrándolo mediante una gramática regular y finalmente convirtiendo cada corchete en una palabra en el lenguaje CFG.

Referencias

1. Chomsky, N.; Schützenberger, MP (1 de enero de 1959), Braffort, P.; Hirschberg, D. (eds.), "La teoría algebraica de los lenguajes libres de contexto*", Estudios de lógica y fundamentos de las matemáticas , Programación informática y sistemas formales, vol. 26, Elsevier, págs. 118-161, doi :10.1016/S0049-237X(09)70104-1, ISBN 978-0-444-53391-3, consultado el 28 de septiembre de 2024

• Autebert, Jean-Michel; Berstel, Jean; Boasson, Luc (1997). "Lenguajes libres de contexto y autómatas de inserción" (PDF) . En G. Rozenberg y A. Salomaa, eds., Handbook of Formal Languages, vol. 1: Word, Language, Grammar (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.). Elsevier Science. pág. 306. ISBN 0-12-206382-1.