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

Цель работы:

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

Задание на лабораторную работу

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

Разработать программное средство, реализующее следующие функции:

а) ввод произвольной формальной грамматики и проверка ее на принадлежность к классу КС-грамматик;

б) построение МП-автомата по КС-грамматике;

в) построение расширенного МП-автомата по КС-грамматике.

Продемонстрировать разбор некоторой входной строки с помощью построенных автоматов для случая:

а) входная строка принадлежит языку исходной КС-грамматики и допускается МП-автоматом;

б) входная строка не принадлежит языку исходной КС-грамматики и не принимается МП-автоматом.

5

G=({R, T, F, G, K}, {m, i, j, k, ^, ~, ^}, P, R), где P:

1) R®R~T^ | R^T^ | e; 2) T®F | Fi | Fj | Gk | e; 3) G®GkG;

4) K®Ki | Km | m.