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