Теорема Грейбаха - Greibachs theorem - Wikipedia

В теоретическая информатика, в частности в формальная теория языка, Теорема Грейбаха заявляет, что определенные свойства формальный язык классы неразрешимый. Он назван в честь компьютерного ученого. Шейла Грейбах, которые впервые это доказали в 1963 году.^[1][2]

Определения

Учитывая множество Σ, часто называемое «алфавитом», (бесконечное) множество всех струны построенный из элементов Σ, обозначается Σ^*.A формальный язык является подмножеством Σ^*.Если L₁ и L₂ формальные языки, их товар L₁L₂ определяется как множество { ш₁ш₂ : ш₁ ∈ L₁, ш₂ ∈ L₂ } из всех конкатенации строки ш₁ из L₁ со шнурком ш₂ из L₂.Если L формальный язык и а является символом из Σ, их фактор L/а определяется как множество { ш : ва ∈ L } всех строк, которые можно сделать членами L добавив аИз теории формального языка известны различные подходы к обозначению формального языка конечным описанием, таким как формальная грамматика или конечный автомат.

Например, используя алфавит Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, множество Σ^* состоит из всех (десятичных представлений) натуральных чисел с разрешенными ведущими нулями и пустой строки, обозначаемой как ε. L_div3 всех натуральных чисел, делящихся на 3, является бесконечным формальным языком над Σ; его можно окончательно описать следующим регулярная грамматика с начальный символ S₀:

S0 →	ε |	0 S0	| 1 S2	| 2 S1	| 3 S0	| 4 S2	| 5 S1	| 6 S0	| 7 S2	| 8 S1	| 9 S0
S1 →		0 S1	| 1 S0	| 2 S2	| 3 S1	| 4 S0	| 5 S2	| 6 S1	| 7 S0	| 8 S2	| 9 S1
S2 →		0 S2	| 1 S1	| 2 S0	| 3 S2	| 4 S1	| 5 S0	| 6 S2	| 7 S1	| 8 S0	| 9 S2

Примеры конечных языков: {ε, 1,2} и {0,2,4,6,8}; их произведение {ε, 1,2} {0,2,4,6,8} дает четные числа до 28. Факторное отношение множества простых чисел до 100 по символу 7, 4 и 2 дает язык {ε, 1,3,4,6,9}, {} и {ε} соответственно.

Формальная формулировка теоремы

Теорема Грейбаха не зависит от конкретного подхода к описанию формального языка, она просто рассматривает множество C формальных языков над алфавитом Σ∪ {#} такой, что

• каждый язык в C имеет конечное описание,
• каждый регулярный язык над Σ∪ {#} находится в C,^{[примечание 1]}
• данные описания языков L₁, L₂ ∈ C и регулярного языка р ∈ C, описание продуктов L₁р и RL₁, и союза L₁∪L₂ можно эффективно вычислить, и
• это неразрешимо для любого языка участников L ∈ C с L ⊆ Σ^* ли L = Σ^*.

Позволять п любое нетривиальное подмножество C содержащий все регулярные множества над Σ∪ {#} и замкнутый относительно частное каждым отдельным символом в Σ∪ {#}.^{[заметка 2]}Тогда вопрос: L ∈ п для данного описания языка L ∈ C неразрешима.

Доказательство

Позволять M ⊆ Σ^*, так что M ∈ C, но M ∉ п.^{[заметка 3]}Для любого L ∈ C с L ⊆ Σ^*определим φ (L) = (M# Σ^*) ∪ (Σ^*#L) .Из описания L, описание φ (L) можно эффективно вычислить.

потом L = Σ^* тогда и только тогда, когда φ (L) ∈ п:

• Если L = Σ^*, то φ (L) = Σ^*# Σ^* является регулярным языком, поэтому в п.
• Еще некоторые ш ∈ Σ^* \ L существует, а фактор φ (L)/(#ш) равно M. Следовательно, многократно применяя свойство фактор-замыкания, φ (L) ∈ п означало бы M = φ (L)/(#ш) ∈ п, что противоречит определению M.

Следовательно, если членство в п была бы разрешима при φ (L) из его описания, так будет LРавенство Σ^* из его описания, что противоречит определению C.^[3]

Приложения

Используя теорему Грейбаха, можно показать, что следующие проблемы неразрешимы:

• Учитывая контекстно-свободная грамматика, описывает ли он обычный язык ?

Доказательство: Класс контекстно-свободных языков и набор обычных языков удовлетворяют указанным выше свойствам C, и п, соответственно.^{[примечание 4][4]}

• Учитывая контекстно-свободный язык, это по своей сути неоднозначный ?

Доказательство: Класс контекстно-свободных языков и набор контекстно-свободных языков, которые не являются неоднозначными по своей сути, удовлетворяют указанным выше свойствам C, и п, соответственно.^[5]

• Учитывая контекстно-зависимая грамматика, описывает ли он контекстно-свободный язык ?

Смотрите также Грамматика без контекста # Находиться на более низком или более высоком уровне иерархии Хомского.

Примечания

1. Это неявно остается в Hopcroft, Ullman, 1979: п ⊆ C должен содержать все эти обычные языки.
2. То есть, если L ∈ п, тогда L/а ∈ п для каждого а ∈ Σ∪ {#}.
3. Существование такого M требуется в соответствии с приведенным выше несколько расплывчатым требованием п будучи «нетривиальным».
4. Обычные языки не зависят от контекста: Грамматика без контекста # Подклассы; контекстно-свободные языки закрыты относительно объединения и (даже общего) объединения: Контекстно-свободная грамматика # Свойства замыкания; равенство Σ^* неразрешимо для контекстно-свободных языков: Бесконтекстная грамматика # Универсальность; регулярные языки закрыты относительно (даже общих) факторов: Обычный язык # Свойства закрытия.

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

1. Шейла Грейбах (1963). «Неразрешимость проблемы неоднозначности для минимальных линейных грамматик». Информация и контроль. 6 (2): 117–125. Дои:10.1016 / s0019-9958 (63) 90149-9.
2. Шейла Грейбах (1968). «Заметка о неразрешимых свойствах формальных языков». Теория математических систем. 2 (1): 1–6. Дои:10.1007 / bf01691341.
3. Джон Э. Хопкрофт; Джеффри Д. Уллман (1979). Введение в теорию автоматов, языки и вычисления. Эддисон-Уэсли. ISBN  0-201-02988-X. стр.205-206
4. Хопкрофт, Ульман, 1979, с.205, теорема 8.15
5. Хопкрофт, Ульман, 1979, с.206, теорема 8.16.