Ну, в первом случае автомат с магазинной памятью, во втором случае просто автомат. Делаем новый автомат с магазинной памятью, объединяющий два имеющихся. Получается новая КС-грамматика.

Наверное как-то так же предполагалось и вычитать регулярные выражения из КС-грамматики. Регулярное выражение можно инвертировать, а полученное инвертированное сложить с грамматикой.

картинки:
http://web.cs.wpi.edu/~kal/courses/fcs/module7/grahneclass12.pdf
"The intersection of a context-free language and a regular language is a context-free language"

см. также Вычитание регэкспов, операция "опровержения"

Отредактировано Лис (2018-01-03 12:39:56)