Проблема пустоты
В теоретической информатике и теории формального языка формальный язык пуст , если его набор допустимых предложений является пустым набором . Проблема пустоты — это вопрос определения того, является ли язык пустым при некотором его представлении, например, автомате с конечным числом состояний . [1] Для автомата, имеющего утверждает, что это проблема принятия решений , которая может быть решена в время , [2] или во времени если автомат имеет n состояний и m переходов. Однако варианты этого вопроса, такие как проблема пустоты для нестирающих стековых автоматов , являются PSPACE-полными . [3]
Проблема пустоты неразрешима для контекстно-зависимых грамматик , и этот факт следует из неразрешимости проблемы остановки . Однако это разрешимо для контекстно-свободных грамматик . [3]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Сипсер, Майкл (2012). Введение в теорию вычислений . Cengage Обучение. ISBN 9781285401065 .
- ^ «Лекция 6: Свойства регулярных языков – II» . COMS W3261 Теория CS . Кафедра компьютерных наук Колумбийского университета . Архивировано из оригинала 31 октября 2019 г. Проверено 22 августа 2019 г.
- ^ Jump up to: а б Хопкрофт, JE ; Ульман, Дж. Д. (1979). Введение в теорию автоматов, языки и вычисления (первое изд.). Аддисон-Уэсли . ISBN 81-7808-347-7 .
 | Эта по информатике статья незавершена . Вы можете помочь Википедии, расширив ее . |