Во многих работах с использованием контекстно-свободных грамматик (CFG) примеры таких грамматик, представленные там, часто допускают простую характеристику языка, который они генерируют. Например: S→aaSbS→aaSbS \to a a S b S→S→S \to генерирует {a2ibi|i≥0}{a2ibi|i≥0}\{ a^{2i} b^i | i \geq 0\} ,...
Мне интересно, есть ли какие-либо статьи или исследования, посвященные явно выталкивающим автоматам, но позволяющие помещать слова, а не отдельные буквы, в стек. С другой стороны, конструкция, которая позволяла нажимать символы на ϵϵ\epsilon переходы, могла бы достичь той же цели. Очевидно, что...
РЕДАКТИРОВАТЬ (Тара B): Я все еще был бы заинтересован в ссылке на доказательство этого, так как я должен был доказать это сам для моей собственной статьи. Я ищу доказательство теоремы 4, которое появляется в этой статье: Бесконечная иерархия пересечений контекстно-свободных языков Лю и Вейнера....
Пусть будет контекстно-свободным языком. Определить , чтобы быть пре- и постфиксное замыканием , другими словами, содержит все «с префиксами и postfixes, и , следовательно сам по себе. Мой вопрос: если зависит от контекста и имеет не однозначную грамматику, то же самое верно для ?p p c ( L ) L p p...