@Guru_one

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

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

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

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

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

P.S Заранее прошу прощение за возможно не совсем точное изложение вопроса или ошибки в терминологии (учусь на немецком языке, поэтому пришлось интуитивно переводить суть задания)
  • Вопрос задан
  • 97 просмотров
Решения вопроса 1
wataru
@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
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Clain Санкт-Петербург
от 80 000 ₽
Devmasterz Санкт-Петербург
от 60 000 до 100 000 ₽
27 сент. 2021, в 15:31
1200 руб./в час
27 сент. 2021, в 15:28
20000 руб./за проект
27 сент. 2021, в 15:28
1200 руб./в час