Детерминированный контекстно-свободный язык
В формального языка теории детерминированные контекстно-свободные языки ( 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] Это очень важно для перевода на компьютерные языки , поскольку многие компьютерные языки принадлежат к этому классу языков.
См. также
[ редактировать ]- Контекстно-свободный язык
- Детерминированный автомат с выталкиванием
- Детерминированная контекстно-свободная грамматика
- Простой детерминированный язык
Ссылки
[ редактировать ]- ^ Хопкрофт, Джон ; Джеффри Уллман (1979). Введение в теорию автоматов, языки и вычисления . Аддисон-Уэсли. п. 233.
- ^ Хопкрофт, Джон ; Раджив Мотвани ; Джеффри Уллман (2001). Введение в теорию автоматов, языки и вычисления, 2-е издание . Аддисон-Уэсли. стр. 249–253.
- ^ Кук, Стивен А. (30 апреля – 2 мая 1979 г.). «Детерминированные КЛЛ принимаются одновременно в полиномиальном времени и логарифмическом пространстве». Материалы одиннадцатого ежегодного симпозиума ACM по теории вычислений - STOC '79 . Атланта. стр. 338–345. дои : 10.1145/800135.804426 .
- ^ Jump up to: а б Хугебум, Хендрик; Энгельфрит, Йост (2004). Формальные языки и приложения . Шпрингер-Верлаг Берлин Гейдельберг. п. 128. ИСБН 978-3-642-53554-3 .
- ^ Кнут, DE (июль 1965 г.). «О переводе языков слева направо» . Информация и контроль . 8 (6): 607–639. дои : 10.1016/S0019-9958(65)90426-2 .