Левая грамматика

В формального языка теории левая грамматика — это формальная грамматика , в которой наложены определенные ограничения на левую и правую части грамматики. Допускаются только два вида производств, а именно вида $a\to ba$ (правила вставки) и $cd\to d$ (правила удаления). Здесь, $a,b,c$ и $d$ являются терминальными символами. Этот тип грамматики был вызван проблемами доступности в области компьютерной безопасности . ^[1]

Вычислительные свойства

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

Проблема принадлежности левых грамматик разрешима. ^[1]

См. также

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

Теория автоматов : формальные языки и формальные грамматики.

Иерархия Хомского	Грамматика	Языки	Абстрактные машины
Тип-0 — Тип-1 — — — — — Тип-2 — — Тип-3 — —	Неограниченный (нет общего имени) Контекстно-зависимый положительного диапазона Конкатенация Индексировано — Линейные контекстно-свободные системы переписывания Примыкание к дереву Контекстно-свободный Детерминированный контекстно-свободный Заметное нажатие вниз Обычный — Нерекурсивный	Рекурсивно перечислимый разрешимый Контекстно-зависимый положительного диапазона Конкатенация ^* Индексировано ^* — Линейный контекстно-свободный язык переписывания Примыкание к дереву Контекстно-свободный Детерминированный контекстно-свободный Заметное нажатие вниз Обычный Без звезд Конечный	Машина Тьюринга Решающий Линейно ограниченный PTIME Машина Тьюринга Вложенный стек Нить-автомат ограниченный автомат стека дерева Встроенный раскрывающийся список Недетерминированное нажатие вниз Детерминированное понижение Заметное нажатие вниз Конечный Без счетчиков (с апериодическим конечным моноидом) Ациклический конечный

Каждая категория языков, кроме отмеченных значком ^*, является правильным подмножеством категории, расположенной непосредственно над ним. Любой язык в каждой категории порождается грамматикой и автоматом в категории в одной строке.

Ссылки

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

^ Jump up to: ^а ^б Мотвани, Раджив; Паниграхи, Рина; Сарасват, Виджай; Венткатасубраманиан, Суреш (2000). «О разрешимости проблем доступности (расширенный тезис)». Материалы тридцать второго ежегодного симпозиума ACM по теории вычислений - STOC '00 . Материалы тридцать второго ежегодного симпозиума ACM по теории вычислений (STOC '00). стр. 306–315. дои : 10.1145/335305.335341 . ISBN 1581131844 .