Verxi el menu prinsipałe

Teorema de enumerassion de Chomsky–Schützenberger

Sta pajina xè orfana
Sta pajina de sienseorfana, overo priva de cołegamenti in entrata da altre pajine
Inserissighene almanco uno pertinente e cava l'avixo
Sta pajina xè orfana

In te 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.'

FormulassionModìfega

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  .