Как можно определить язык, который не вписывается в Иерархию Хомского? - PullRequest
Новая
       51

Как можно определить язык, который не вписывается в Иерархию Хомского?

0 голосов
/ 12 июля 2020

Я задаю этот вопрос, потому что наткнулся на принятый ответ Типы языков Хомского

Эта цитата относится к грамматикам типа 0:

Это означает, что если у вас есть язык, который более выразителен, чем этот тип (например, Engli sh) , вы не можете написать алгоритм, который может перечислить каждое (и только эти) слова из язык

Насколько я знаю:

  • Нет математического описания того, что такое Engli sh, поэтому бессмысленно спорить о том, где он находится в иерархия формальных языков.
  • Если бы это было так, то Engli sh определенно был бы узнаваем с помощью некоторой грамматики типа 0 в силу того, что он определяется конечным количеством рассуждений - где это аксиомы, грамматика , что-нибудь. (Если нет - как бы кто-то мог определить это, если не конечным количеством шагов?)

Отсюда:

  • Мы не можем начать говорить о том, как ' выразительный 'грамматика должна генерировать точно неизвестный математический объект

Поэтому моя проблема:

  • Как можно определить язык, который не вписывается в Иерархию Хомского?
  • Если (?) математикам требуется конечное количество шагов, чтобы определить множества с мощностями, которые не делают их рекурсивно перечисляемыми, - тогда должны существовать грамматики, которые являются более выразительными, чем Тип-0, поскольку они (математики) следовали конечному количеству правил (производственным правилам, если хотите), чтобы создать не-RE набор. Где они?

1 Ответ

2 голосов
/ 13 июля 2020

Язык - это возможно бесконечное множество конечных слов, написанных некоторым конечным алфавитом. Поскольку алфавит конечен, а длина каждого слова конечна, слова любого языка перечислимы в том смысле, что существует перечисление. Другими словами, размер любого языка не более чем счетно бесконечен.

Однако, поскольку любое подмножество замыкания Клини в алфавите является языком, количество языков не бесконечно. Следовательно, нет никакого перечисления языков. символы). [Примечание 1] Таким образом, количество возможных грамматик Типа 0 счетно бесконечно, и не может быть соответствия между набором грамматик и набором языков.

Однако. Существование языков (то есть наборов), для которых не существует порождающей грамматики, не обязательно означает, что существует какой-то другой способ описания этих языков, который является «более выразительным», чем порождающие грамматики. Любое описание, которое может быть записано в виде конечной строки с использованием конечного алфавита, может описывать только счетное бесконечное множество множеств. Будет ли это одна и та же счетная бесконечность, будет зависеть от формализмов, и вообще не будет никакого алгоритма, который может продемонстрировать гомоморфизм. Но некоторые эквивалентности известны (например, эквивалентность с машинами Тьюринга, которая является особенно интересной эквивалентностью).

Итак, у нас есть интересная небольшая загадка, которая (конечно) связана с теоремами Гёделя о неполноте. То есть языков больше, чем способов описания языка, независимо от того, какую систему мы используем для описания языка. Итак, вопрос «Как мы можем описать язык, для которого нет описания?» не имеет хорошего ответа (и если мы ответим на него, вызвав некоторый набор "Сью", то все равно будет бесчисленное множество возможных наборов, для которых не существует имени).

Пока все это собиралось в infinitude интересен, у него есть несколько проблем:

  1. Он имеет очень мало (если вообще имеет) отношение к программированию, поэтому сомнительно, что он включен в topi c для StackOverflow.

  2. Курт Гёдель и Георг Кантор, два математика, ответственные за большинство концепций в этом ответе, оба страдали тяжелой депрессией. Просто говорю.

Примечания

  1. Хотя на первый взгляд может показаться, что алфавит для грамматики типа 0 может быть произвольно больше, чем алфавит описываемого языка, на самом деле это не так. Алфавит грамматики состоит из целевого алфавита плюс конечного набора нетерминалов и символа →; нетерминалы могут быть записаны с использованием чисел в любой удобной основе, например, в двоичной системе. Таким образом, требуются только три дополнительных символа (и вы можете уменьшить их до двух, произвольно назначив одно из нетерминальных чисел стрелкой). (Может показаться, что вам нужен третий символ для разграничения имен нетерминалов, но вы можете использовать кодировку Фибоначчи для создания кодов, которые всегда начинаются с 1 и никогда не включают две единицы, так что вы можете использовать дополнительную 1 в начало однозначно обозначить начало символа.)
...