Контекстно-зависимый язык

• Определение и примеры контекстно-зависимых языков

  • Контекстно-зависимые языки — это языки, которые могут быть приняты недетерминированными автоматами Тьюринга с линейным пространством. 
  • Примеры контекстно-зависимых языков включают строки с одинаковым количеством символов «a», «b» и «c». 

• Примеры контекстно-зависимых языков

  • L — это язык, состоящий из строк с одинаковым количеством символов «a», «b» и «c». 
  • L Пересекать — это язык, состоящий из строк, где «a», «b» и «c» встречаются одинаково часто. 
  • L MUL3 — это язык, определяемый операцией «product» над троичным алфавитом. 
  • L REXP — это язык, состоящий из строк с экспоненциальной длиной. 
  • L ПРОСТЫЕ ЧИСЛА2 — это язык, состоящий из строк с простыми числами. 
  • L ПРОСТЫЕ ЧИСЛА1 — это язык, состоящий из строк с простыми числами в унарной записи. 

• Свойства контекстно-зависимых языков

  • Объединение, пересечение и конкатенация контекстно-зависимых языков зависят от контекста. 
  • Дополнение контекстно-зависимого языка также является контекстно-зависимым. 
  • Принадлежность строки к контекстно-зависимому языку является проблемой с заполнением PSPACE. 

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

  • Сипсер, М. (1996). «Введение в теорию вычислений». PWS Publishing Co.