Построение автомата с магазинной памятью по контекстно-свободной грамматике (на С#)

Начальной конфигурацией МП-автомата является конфигурация
(q0, ω, N0).
Шаг работы МП-автомата будем представлять в виде отношения непосредственного следования конфигураций (обозначается «|=») и отношения достижимости конфигураций (обозначается «|=*»). Если одним из значений магазинной функции F(q ∈ Q,t ∈ (T ∪ {ε}),S ∈ N) является
(qʹ ∈ Q, γ ∈ N^*), то записывается (q,t ω,Sα) |=(qʹ, ω,γα). При этом возможны следующие варианты.

Тема: «Построение автомата с магазинной памятью по контекстно-свободной грамматике»
Цель:
- закрепить понятия «автомат с магазинной памятью (МП-автомат)», «расширенный МП-автомат», «конфигурация МП-автомата»; «строка и язык, допускаемые МП-автоматом»;
- сформировать умения и навыки построения МП-автомата и расширенного МП-автомата по КС-грамматике, разбора входной строки с помощью МП-автомата.

!!! В прикрепленном файле расширение doc поменять на zip !!!
на С#

Разработать программное средство, реализующее следующие функции:
а) ввод произвольной формальной грамматики и проверка ее на принадлежность к классу КС-грамматик;
б) построение МП-автомата по КС-грамматике;
в) построение расширенного МП-автомата по КС-грамматике;
Продемонстрировать разбор некоторой входной строки с помощью построенных автоматов для случая:
а) входная строка принадлежит языку исходной КС-грамматики и допускается МП-автоматом;
б) входная строка не принадлежит языку исходной КС-грамматики и не принимается МП-автоматом.

Вариант 3: КС-грамматика G=({S, R, T, X, Y}, {a, b, p, g, y}, P, S), где P:
1) S→R | T
2) R→pX | paR | paT | ε
3) T→Tg | g
4) X→aXb
5) Y→aYa | y