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  xe naserie che no finisse de la forma

che la ga moltiplicatori sconossudi  che li sta tuti drento .

La moltiplicassion de do serie de potense formałi  e  xe circoscrita come che ce se speta dixendo che xe la convolussion de le sequense  e :

Sol specifio, scrivemo , , e vanti cussì.

In maniera compagna de i numeri aldebrici, na serie de potense  xe dita aldebrica so , se drento ghe xe un insieme finito de polinomi  ciascun co moltiplicatori sconossudi rassionali

e in maniera che

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  xe un linguagio libaro dal contesto che permete na gramatica non ambigua e libara dal contesto, e  xe el numaro de parołe de lunghessa  drento , 
elora  xe na serie de potense so  che xe aldebrica so .

Categoria:Matemàtega