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

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

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

Математика

Обозначение

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

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

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

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

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

Теорема

Язык 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.

Ссылки

1. Хомский, Н.; Шютценбергер, М. П. (1959-01-01), Браффорт, П.; Хиршберг, Д. (ред.), «Алгебраическая теория контекстно-свободных языков*», Исследования по логике и основам математики , компьютерное программирование и формальные системы, т. 26, Elsevier, стр. 118–161, doi :10.1016/S0049-237X(09)70104-1, ISBN 978-0-444-53391-3, получено 2024-09-28

• Отеберт, Жан-Мишель; Берстель, Жан; Боассон, Люк (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.