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

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

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

Описание

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

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

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

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

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

Множество детерминированного контекстно-свободного языка не замыкается при выполнении следующих операций: ^{[ 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 .

[1] Хопкрофт, Джон ; Джеффри Уллман (1979). Введение в теорию автоматов, языки и вычисления . Аддисон-Уэсли. п. 233.

[2] Хопкрофт, Джон ; Раджив Мотвани ; Джеффри Уллман (2001). Введение в теорию автоматов, языки и вычисления, 2-е издание . Аддисон-Уэсли. стр. 249–253.

[3] Кук, Стивен А. (30 апреля – 2 мая 1979 г.). «Детерминированные КЛЛ принимаются одновременно в полиномиальном времени и логарифмическом пространстве». Материалы одиннадцатого ежегодного симпозиума ACM по теории вычислений - STOC '79 . Атланта. стр. 338–345. дои : 10.1145/800135.804426 .

[Formal_Languages_and_Applications-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 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]