Соотношения между иерархией Хомского и грамматиками Ламбека

Доклад в основном будет посвящен доказательству так называемой гипотезы Хомского (Пентус 1993): языки, генерируемые грамматиками Ламбека, являются контекстно-свободными. Мы начнем с рассмотрения AB-грамматик — на первый взгляд более слабого формализма, который по своей описательной мощности уже эквивалентен контекстно-свободным грамматикам. Мы посмотрим, как любую контекстно-свободную грамматику можно превратить в эквивалентную ей AB-грамматику, что является одним из ключевых моментов в доказательстве обратной гипотезы Хомского, и перейдем к собственно грамматикам Ламбека. Далее мы обсудим некоторые лингвистические причины того, почему они лучше подходят для описания различных языковых явлений по сравнению с AB-грамматиками, и начнем доказывать гипотезу Хомского, параллельно проводя основные необходимые технические выкладки.