Teorema de enumerassion de Chomsky–Schützenberger

Inte la teoria de i linguagi formałi, el Teorema de enumerassion de'Chomsky–Schützenberger xe un teorema formulà da Noam Chomsky e Marcel-Paul Schützenberger chel riguarda el numaro de paroe de lunghessa predefinìa generade da na gramatica non ambigua libara dal contesto. El teorema el fornisse un gròpo inaspettà chel taca la teorìa de i linguagi formałi insieme co l'aldebra astrata.'

Formulassion

Prima de formular el teorema, ghe vol na s-cianta de conosiense de aldebra e teoria dei linguagi formałi.

Na serie de potense so $\mathbb {N}$ xe naserie che no finisse de la forma

$f=f(x)=\sum _{k=0}^{\infty }a_{k}x^{k}=a_{0}+a_{1}x^{1}+a_{2}x^{2}+a_{3}x^{3}+\cdots$

che la ga moltiplicatori sconossudi $a_{k}$ che li sta tuti drento $\mathbb {N}$.

La moltiplicassion de do serie de potense formałi $f$ e $g$ xe circoscrita come che ce se speta dixendo che xe la convolussion de le sequense $a_{n}$ e $b_{n}$:

$f(x)\cdot g(x)=\sum _{k=0}^{\infty }\left(\sum _{i=0}^{k}a_{i}b_{k-i}\right)x^{k}.$

Sol specifio, scrivemo $f^{2}=f(x)\cdot f(x)$, $f^{3}=f(x)\cdot f(x)\cdot f(x)$, e vanti cussì.

In maniera compagna de i numeri aldebrici, na serie de potense $f(x)$ xe dita aldebrica so $\mathbb {Q} (x)$, se drento ghe xe un insieme finito de polinomi $p_{0}(x),p_{1}(x),p_{2}(x),\ldots ,p_{n}(x)$ ciascun co moltiplicatori sconossudi rassionali

e in maniera che

$p_{0}(x)+p_{1}(x)\cdot f+p_{2}(x)\cdot f^{2}+\cdots +p_{n}(x)\cdot f^{n}=0.$

Na grammadega libara dal contesto se dixe che no la xe ambigua se ciascuna stringa che nasse da chela gramadega consente un albaro de analisi unico, o ala stessa maniera solo una derivassion pì a sinistra.

Desso che ghemo stabilio chel che serve da saver, el teorema xe formulà cussì:

Teorema de Chomsky–Schützenberger: Se $L$ xe un linguagio libaro dal contesto che permete na gramatica non ambigua e libara dal contesto, e $a_{k}:=|L\ \cap \Sigma ^{k}|$ xe el numaro de parołe de lunghessa $k$ drento $L$,

elora $G(x)=\sum _{k=0}^{\infty }a_{k}x^{k}$ xe na serie de potense so $\mathbb {N}$ che xe aldebrica so $\mathbb {Q} (x)$.