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

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

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

• 1 Описание
• 2 Свойства
• 3 Важность
• 4 См. Также
• 5 Ссылки

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

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

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

• дополнение
• обратный гомоморфизм
• правое частное с обычным языком
• pre: pre ($L\; \{\backslash \; displaystyle\; L\}$) - это подмножество всех строк, имеющих правильный префикс, который также принадлежит $L\; \{\backslash \; displaystyle\; L\}$.
• min: min ($L\; \{\backslash \; displaystyle\; L\}$) - это подмножество всех строк, у которых нет правильного префикса в $L\; \{\backslash \; displaystyle\; L\; \}$.
• max: max ($L\; \{\backslash \; displaystyle\; L\}$) - это подмножество всех строк, которые не являются префиксом более длинной строки в $L\; \{\backslash \; displaystyle\; L\}$.

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

• объединение
• пересечение
• конкатенация
• звезда Клини
• ε-свободный морфизм
• Зеркальное отображение

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

• Контекстно-свободный язык
• Детерминированный автомат проталкивания
• Детерминированная контекстно-свободная грамматика
• Простой детерминированный язык

1. ^Хопкрофт, Джон; Джеффри Уллман (1979). Введение в теорию автоматов, языки и вычисления. Эддисон-Уэсли. п. 233.
2. ^Хопкрофт, Джон; Раджив Мотвани ; Джеффри Уллман (2001). Введение в теорию автоматов, языки и вычисления 2-е издание. Эддисон-Уэсли. С. 249–253.
3. ^Кук, Стивен А. (30 апреля - 2 мая 1979 г.). «Детерминированные CFL принимаются одновременно в полиномиальное время и в логарифмическом квадрате пространства». Материалы одиннадцатого ежегодного симпозиума ACM по теории вычислений - STOC '79. Атланта. С. 338–345. doi : 10.1145 / 800135.804426.
4. ^ Хугебум, Хендрик; Энгельфриет, Джуст (2004). Формальные языки и приложения. Springer-Verlag Berlin Heidelberg. п. 128. ISBN 978-3-642-53554-3.
5. ^Кнут Д. Э. (июль 1965 г.). «О переводе языков слева направо» (PDF). Информация и контроль. 8 (6): 607–639. DOI : 10.1016 / S0019-9958 (65) 90426-2. Архивировано из исходного (PDF) 15 марта 2012 г. Дата обращения 29 мая 2011 г. CS1 maint: ref = harv (link )