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

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

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

Описание

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

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

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

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

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

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

Важность

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

Смотрите также

Рекомендации