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

В теоретическая информатика и формальная теория языка, формальный язык пустой если его набор действительных предложений пустой набор. В проблема пустоты это вопрос определения того, является ли язык пустым при некотором его представлении, таком как конечный автомат.^[1] Для автомата, имеющего ${\displaystyle n}$ заявляет, что это проблема решения это может быть решено в ${\displaystyle O(n^{2})}$ время.^[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.