Jump to content

Детерминированный контекстно-свободный язык

В формального языка теории детерминированные контекстно-свободные языки ( DCFL ) являются подмножеством контекстно -свободных языков . Это контекстно-свободные языки, которые могут быть приняты детерминированным автоматом с выталкиванием вниз . DCFL всегда однозначны, то есть допускают однозначную грамматику . Существуют недетерминированные однозначные КЛЛ, поэтому DCFL образуют правильное подмножество однозначных КЛЛ.

DCFL представляют большой практический интерес, поскольку их можно анализировать за линейное время , а различные ограниченные формы DCFG допускают простые практические анализаторы. Таким образом, они широко используются в информатике.

Описание

[ редактировать ]

Понятие DCFL тесно связано с детерминированным автоматом с выталкиванием (DPDA). Именно здесь языковая мощь автоматов с выталкиванием сводится к минимуму, если мы сделаем их детерминированными; автоматы с выталкиванием становятся неспособными выбирать между различными альтернативами перехода состояний и, как следствие, не могут распознавать все контекстно-свободные языки. [1] Однозначные грамматики не всегда создают DCFL. четной длины Например, язык палиндромов в алфавите 0 и 1 имеет однозначную контекстно-свободную грамматику S → 0S0 | 1С1 | е. Произвольная строка этого языка не может быть проанализирована без предварительного чтения всех ее букв, а это означает, что автомату с выталкиванием вниз приходится пробовать альтернативные переходы состояний, чтобы приспособиться к различным возможным длинам полуразобранной строки. [2]

Характеристики

[ редактировать ]

Детерминированные контекстно-свободные языки могут быть распознаны детерминированной машиной Тьюринга за полиномиальное время и O (log 2 п ) пространство; как следствие, DCFL является подмножеством класса сложности SC . [3]

Множество детерминированных контекстно-свободных языков замыкается при выполнении следующих операций: [4]

  • дополнять
  • обратный гомоморфизм
  • правильное частное с регулярным языком
  • за: за( ) — это подмножество всех строк, имеющих правильный префикс, который также принадлежит .
  • мин: мин( ) — это подмножество всех строк, которые не имеют правильного префикса в .
  • Макс: Макс( ) — это подмножество всех строк, которые не являются префиксом более длинной строки в .

Множество детерминированного контекстно-свободного языка не замыкается при выполнении следующих операций: [4]

Важность

[ редактировать ]

Языки этого класса имеют большое практическое значение в информатике, поскольку их синтаксический анализ гораздо эффективнее, чем недетерминированные контекстно-свободные языки. Сложность программы и время выполнения детерминированного автомата с выталкиванием значительно меньше, чем у недетерминированного. В простой реализации последний должен делать копии стека каждый раз, когда происходит недетерминированный шаг. Самый известный алгоритм проверки принадлежности к любому контекстно-свободному языку — это алгоритм Валианта , принимающий O( n 2.378 ) время, где n — длина строки. С другой стороны, детерминированные контекстно-свободные языки могут быть приняты за время O( n ) анализатором LR( k ) . [5] Это очень важно для перевода на компьютерные языки , поскольку многие компьютерные языки принадлежат к этому классу языков.

См. также

[ редактировать ]
  1. ^ Хопкрофт, Джон ; Джеффри Уллман (1979). Введение в теорию автоматов, языки и вычисления . Аддисон-Уэсли. п. 233.
  2. ^ Хопкрофт, Джон ; Раджив Мотвани ; Джеффри Уллман (2001). Введение в теорию автоматов, языки и вычисления, 2-е издание . Аддисон-Уэсли. стр. 249–253.
  3. ^ Кук, Стивен А. (30 апреля – 2 мая 1979 г.). «Детерминированные КЛЛ принимаются одновременно в полиномиальном времени и логарифмическом пространстве». Материалы одиннадцатого ежегодного симпозиума ACM по теории вычислений - STOC '79 . Атланта. стр. 338–345. дои : 10.1145/800135.804426 .
  4. ^ Jump up to: а б Хугебум, Хендрик; Энгельфрит, Йост (2004). Формальные языки и приложения . Шпрингер-Верлаг Берлин Гейдельберг. п. 128. ИСБН  978-3-642-53554-3 .
  5. ^ Кнут, DE (июль 1965 г.). «О переводе языков слева направо» . Информация и контроль . 8 (6): 607–639. дои : 10.1016/S0019-9958(65)90426-2 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 0b70a7456972bc26ae30eb3c36250e8f__1667030820
URL1:https://arc.ask3.ru/arc/aa/0b/8f/0b70a7456972bc26ae30eb3c36250e8f.html
Заголовок, (Title) документа по адресу, URL1:
Deterministic context-free language - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)