V teoretické informatiky , a to zejména v formálních jazyků teorii se Chomsky-Schützenberger věta je reprezentace teorém . Tvrdí, že jakýkoli algebraický jazyk lze vyjádřit pomocí určité konstrukce z jazyka Dyck . V tomto smyslu věta tvrdí, že Dyckovy jazyky jsou „typické“ algebraické jazyky. Tato věta je pojmenována po Noamovi Chomském a Marcel-Paul Schützenbergerovi . Objevuje se v jejich společném článku z roku 1963.
V následujícím prohlášení používáme termín abecední morfismus . Morfismus mezi volnými monoidy se říká, že je abecední, pokud je obrázek písmene písmeno nebo prázdné slovo. Je to ekvivalentním způsobem klesající morfismus , to znamená takový, že délka obrazu slova je vždy menší nebo stejná jako délka slova .
Chomsky-Schützenberger věta - Jazyk je algebraické tehdy a jen tehdy, pokud existuje Dyck jazyk , je racionální jazyk a abecední morphism takový, že
.Tato věta je prokázána v několika učebnicích, například v Automatech a Computability od Dextera Kozena .
Ve výše uvedeném prohlášení racionální jazyk a jazyk Dyck samozřejmě závisí na jazyce, který chceme reprezentovat. Varianta spočívá ve výběru, s trochu komplikovanější konstrukcí, jediného jazyka Dyck, konkrétně jazyka Dyck na dvou párech závorek. Pak máme
Věta - Jazyk je algebraický, právě když je napsán ve formě
,kde je Dyckův jazyk nad dvěma páry závorek, je racionálním jazykem a jsou morfismem.
Ekvivalentně toto tvrzení znamená, že jakýkoli algebraický jazyk je obrazem prostřednictvím racionální transdukce nebo že tento jazyk je generátorem racionálního kuželu algebraických jazyků.
Ve výše uvedeném výroku mohou hrát roli jiné jazyky , například jazyk Dyckových prvočísel nebo jazyky Dyckových dvoustranných prvočísel nebo dvoustranných prvočísel.
Místo nastavení počtu párů v závorkách na dva je jakýkoli počet větší nebo rovný dvěma v pořádku. Na druhou stranu, výsledek přestává platit pro jazyky Dyck na jedné dvojici závorek.
Další varianta, či spíše přesnost, se týká povahy homomorfismu věty. Otázkou je, zda můžeme tento nevymazatelný morfismus předpokládat. Negativní odpověď rychle přijde na mysl: protože Dyckův jazyk neobsahuje slovo délky 1, nelze v obrazovém jazyce získat slovo délky 1. Ve skutečnosti se zdá, že je to jediné omezení. Alexander Okhotin dokázal následující prohlášení:
Věta - Jakýkoli algebraický jazyk , který neobsahuje slovo redukované na písmeno, je napsán ve formě
,kde je jazyk Dyck, je jazyk racionální a je nevymazávajícím morfismem .
Důkaz používá mimo jiné oboustrannou Greibachovu normální formu algebraických gramatik. V této souvislosti stojí za zmínku dvě doplňující se prohlášení ze stejného článku.
Návrh - Jakýkoli algebraický jazyk, který obsahuje pouze slova sudé délky, je napsán ve formě
,kde je jazyk Dyck, je jazyk racionální a je morfismem písmeno k písmenu , tj. zachování délky.
Konečně máme větu podobnou Chomského-Schützenbergerově větě nahrazením jazyka Dyck jazykem Motzkin , tj. Jazykem získaným z jazyka Dyck vložením „neutrálních“ písmen. V jakémkoli množství.
Tvrzení - jakýkoli algebraický jazyk je napsán ve formě
,kde je jazyk Motzkin, je jazyk racionální a je morfismem písmeno k písmenu , tj. zachovává délku.