Поиск языка, генерируемого контекстно-свободной грамматикой

Это вопрос из книги Дракона (я прошу прощения за ошибки перевода, у меня нет англоязычной версии):

Какой язык генерируется этой грамматикой?

$S \rightarrow a S b S \mid b S a S \mid \epsilon$

Я не знаю, что мне здесь делать. Определение в книге о языках говорит об этом (и это почти так в этой главе):

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

Поэтому, если я хочу сделать из этой грамматики «любое» дерево разбора, я могу рекурсивно продолжить его построение, используя только первые два правила. Я немного искал и у меня сложилось впечатление, что каждое правило нужно использовать один раз, но я не уверен. Было бы очень полезно, если бы кто-то смог дать несколько советов по решению подобных проблем.

formal-languages context-free formal-grammars Дан
источник

Подсказка: используйте регулярное выражение

Bartosz Przybylski

Для подсказок смотрите ответы ниже. В ответ на ваш вопрос: нет, нет необходимости использовать каждое правило хотя бы один раз. Начните с начального символа (или аксиомы) и применяйте правила перезаписи, пока у вас не останутся только терминальные символы (здесь строчные буквы).

Хендрик Ян

если предположить, что пустая строка не является терминальным символом, то, насколько я понимаю, невозможно, чтобы остались только терминальные символы, или я что-то не так понимаю?

Дан

Crossposted на cs.SE .

Рафаэль

@dan. Пустая строка исчезает, поэтому вы можете получить только терминалы: . Например.

S \Rightarrow a S b S \Rightarrow a a S b b S \Rightarrow a a b b S \Rightarrow a a b b b S a \Rightarrow a a b b b a

$S \Rightarrow aSbS \Rightarrow aaSbbS \Rightarrow aabbS \Rightarrow aabbbSa \Rightarrow aabbba$

Хендрик Ян

Ответы:

Подсказка: Что вы можете сказать о количестве е и ы в полученных словах? $a$ $b$

Было бы очень полезно, если бы кто-то смог дать несколько советов по решению подобных проблем.

Здесь нет единого рецепта для всех. В общем, неразрешимо, производят ли два CFG один и тот же язык или два CFL - один и тот же язык. Полезный метод - попытаться заметить свойства, которые остаются неизменными во время производства.

Мне.
источник

Подсказка: составьте несколько слов, которые генерируются этой грамматикой. Вы видите образец? Можете ли вы описать некоторые свойства всех слов, генерируемых грамматикой, просто взглянув на правила? Если у вас есть (правильное) предположение относительно языка, генерируемого грамматикой, вам не составит труда доказать это.

Юваль Фильмус
источник