Теорема о представлении Хомского – Шютценбергера

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

Теорема Доказательства этой теоремы можно найти в нескольких учебниках, например, Autebert, Berstel & Boasson (1997) или Davis, Sigal & Weyuker (1994).

Рассмотрим несколько понятий из формальной теории языка.

Контекстно-свободный язык является регулярным , если он может быть описан регулярным выражением или, что эквивалентно, если он принимается конечным автоматом .

Гомоморфизм основан на функции, которая отображает символы из алфавита в слова из другого алфавита ; если область определения этой функции естественным образом расширить до слов из , положив для всех слов и , то это даст гомоморфизм .${\displaystyle ч}$${\displaystyle \Гамма}$${\displaystyle \Сигма}$${\displaystyle \Гамма}$${\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}}\,\}.}$

Например, следующее предложение является допустимым на трехтипном языке Дика:

( [ [ ] { } ] ( ) { ( ) } )

Язык 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)}$

Мы можем интерпретировать это так, что любой язык CFG может быть сгенерирован путем первоначальной генерации типизированного языка Дика, фильтрации его с помощью регулярной грамматики и, наконец, преобразования каждой скобки в слово на языке CFG.

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