Теорема Грейбаха - Википедия - Greibachs theorem

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

Определения

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

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

S0ε |0 S0  | 1 S2  | 2 S1  | 3 S0  | 4 S2  | 5 S1  | 6 S0  | 7 S2  | 8 S1  | 9 S0
S10 S1| 1 S0| 2 S2| 3 S1| 4 S0| 5 S2| 6 S1| 7 S0| 8 S2| 9 S1
S20 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]
  • данные описания языков L1, L2C и регулярного языка рC, описание продуктов L1р и RL1, и союза L1L2 можно эффективно вычислить, и
  • это неразрешимо для любого языка участников LC с L ⊆ Σ* ли L = Σ*.

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

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

Позволять M ⊆ Σ*, так что MC, но Mп.[заметка 3]Для любого LC с 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.