Как построить контекстно-свободную грамматику по мультиграфу автомата с магазинной памятью?

Question

[Guru_one]

Приветствую !
Учусь в университете, проходим сейчас контекстно-свободные грамматики. Я понял как преобразовывать контекстно-свободную грамматику в МП-автоматы, а вот с тем как найти контекстно-свободную грамматику если уже есть автомат возникли проблемы.

Есть следующий МП-автомат (с англ. PDA), этот автомат допускает язык L0 =L(M0)={a^i b^j c^k | i=j или j=k где i, j, k≥1}, который нужно преобразовать в контекстно-свободную грамматику(с англ. CFG):


Если я правильно понимаю, сначала нужно найти правила по которым работает этот автомат и исходя из них построить грамматику. Но с этим и возникли проблемы в данной задаче.

Буду благодарен любым советам!

P.S Заранее прошу прощение за возможно не совсем точное изложение вопроса или ошибки в терминологии (учусь на немецком языке, поэтому пришлось интуитивно переводить суть задания)

Answer 1

[Wataru]

Нет, приведенный автомат принимает язык {a^i b^j c^k | i=j, i>=1, k>=1} - букв c может быть сколько угодно, никак не связанно с количестовом букв b.

Первый переход всегда кладет в стек #. Потом на каждую поглощенную a исходной строки добавиться A в стек. Потом b будет поглащаться вместе с A из стека. Потом поглатиться с из строки и # из стека. В конце может поглотиться сколько-то c.

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

Сначала составьте граматику для языка {a^ib^i, i>=1}. Потом ее можно легко преобразовать чтобы дописывались c.

Граматика для такого языка будет, например:
S -> aSb
S -> e

Для дописывания c в конце:
Z->Zc
Z->S