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