Проблема пустоты - Emptiness problem

В теоретическая информатика и формальная теория языка, формальный язык пустой если его набор действительных предложений пустой набор. В проблема пустоты это вопрос определения того, является ли язык пустым при некотором его представлении, таком как конечный автомат.[1] Для автомата, имеющего заявляет, что это проблема решения это может быть решено в время.[2] Однако варианты этого вопроса, такие как проблема пустоты для не стирающие стековые автоматы, находятся PSPACE-полный.[3]

Проблема пустоты неразрешимый за контекстно-зависимые грамматики, что следует из неразрешимости проблема остановки. Однако это разрешимо для контекстно-свободные грамматики.[3]

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

  1. ^ Сипсер, Майкл (2012). Введение в теорию вычислений. Cengage Learning. ISBN  9781285401065.
  2. ^ «Лекция 6: Свойства регулярных языков - II». COMS W3261 CS Теория. Департамент компьютерных наук, Колумбийский университет. Получено 2019-08-22.
  3. ^ а б Хопкрофт, Дж. Э.; Ульман, Дж. Д. (1979). Введение в теорию автоматов, языки и вычисления (первое изд.). Эддисон-Уэсли. ISBN  81-7808-347-7.