Математическая теория формальных языков

         

Алгоритмически неразрешимые проблемы


В этой лекции рассматриваются оказавшиеся неразрешимыми алгоритмические проблемы, связанные с контекстно-свободными языками. Всюду предполагается, что в индивидуальных задачах каждый язык представлен контекстно-свободной грамматикой (но можно, конечно, использовать и автоматы с магазинной памятью).

В разделе 16.1 доказывается неразрешимость проблемы пустоты пересечения контекстно-свободных языков и проблемы бесконечности пересечения контекстно-свободных языков.

В разделе 16.2 доказывается неразрешимость проблемы однозначности контекстно-свободной грамматики.

В разделе 16.3 доказывается неразрешимость проблемы равенства контекстно-свободных языков.

В разделе 16.4 доказывается неразрешимость проблемы автоматности контекстно-свободного языка.

В разделе 16.5 доказывается неразрешимость проблем контекстной свободности дополнения контекстно-свободного языка и пересечения контекстно-свободных языков.



Содержание раздела