Построить автомат с магазинной памятью и кс-граматику, задающие язык, содержащий те и только те слова в алфавите

Без ограничения на подслово 100 можно взять такие грамматики:

S -> 1S0 | 0S1 | SS | пустое слово

или

S -> 1S0S | 0S1S | пустое слово

По ним легко построить МП-автомат. Далее известно, что класс КС-языков замкнут относительно пересечения с регулярными языками. Автомат, который принимает пересечение, получается как произведение МП-автомата и детерминированного конечного автомата (§7.3.4 в книге Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений. М.: Вильямс, 2008). Теоретически по получившемуся МП-автомату можно построить грамматику, но там, наверное, будет много правил.

Может быть, есть более легкий способ, но пока он не приходит в голову.

См. также

это сообщение

.