Теорема Хомского – Шютценбергера о представлении - Chomsky–Schützenberger representation theorem

В формальная теория языка, то Теорема Хомского – Шютценбергера о представлении это теорема, полученная Ноам Хомский и Марсель-Пауль Шютценбергер о представлении данного контекстно-свободный язык в терминах двух более простых языков. Эти два более простых языка, а именно обычный язык и Язык Дайка, объединяются с помощью пересечение и гомоморфизм.

Приведем несколько понятий из теории формального языка. Контекстно-свободный язык - это обычный, если можно описать регулярное выражение, или, что то же самое, если он принят конечный автомат. Гомоморфизм основан на функции ${\displaystyle h}$ который отображает символы из алфавита ${\displaystyle \Gamma }$ к словам над другим алфавитом ${\displaystyle \Sigma }$; Если область определения этой функции распространяется на слова над ${\displaystyle \Gamma }$ естественным путем, позволяя ${\displaystyle h(xy)=h(x)h(y)}$ для всех слов ${\displaystyle x}$ и ${\displaystyle y}$, это дает гомоморфизм ${\displaystyle h:\Gamma ^{*}\to \Sigma ^{*}}$. А подобранный алфавит ${\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}}\,\}}$

слова, которые заключены в круглые скобки ${\displaystyle T\cup {\overline {T}}}$.

Теорема Хомского – Шютценбергера.. Язык L по алфавиту ${\displaystyle \Sigma }$ контекстно-свободно тогда и только тогда, когда существует

• согласованный алфавит ${\displaystyle T\cup {\overline {T}}}$
• обычный язык ${\displaystyle R}$ над ${\displaystyle T\cup {\overline {T}}}$,
• и гомоморфизм ${\displaystyle h:(T\cup {\overline {T}})^{*}\to \Sigma ^{*}}$

такой, что ${\displaystyle L=h(D_{T}\cap R)}$.

Доказательства этой теоремы можно найти в нескольких учебниках, например. Отеберт, Berstel & Boasson (1997) или же Дэвис, Сигал и Вейкер (1994).

Рекомендации

• Отбер, Жан-Мишель; Берстель, Жан; Боассон, Люк (1997). «Контекстно-свободные языки и автоматические раскрывающиеся списки» (PDF). В G. Rozenberg and A. Salomaa, eds., Справочник формальных языков, Vol. 1. Слово, язык, грамматика (стр. 111–174). Берлин: Springer-Verlag. ISBN  3-540-60420-0.
• Дэвис, Мартин Д .; Сигал, Рон; Вейкер, Элейн Дж. (1994). Вычислимость, сложность и языки: основы теоретической информатики (2-е изд.). Elsevier Science. п. 306. ISBN  0-12-206382-1.