я грамматика определяется следующим образом:Является ли эта контекстно-свободная грамматика регулярным выражением?
A -> aA*b | empty_string
ли A регулярное выражение? Я смущен, как интерпретировать грамматику BNF.
A представляется правилом грамматики BNF. Я не совсем уверен, почему вы путаете это с регулярным выражением. Вы смущены, потому что в нем есть *? Все, что имеет *, не является регулярным выражением.
Что заставляет меня смутить, у нас есть оба слева и справа. Символ * определенно является символом в RegEx, поскольку он сообщает вам, что A повторяет 0 или более раз. – user397232
«Все, что имеет \ *, не является регулярным выражением». Нет, некоторые вещи, которые имеют регулярные выражения \ * _are_. Я думаю, вы имели в виду, что не все вещи, которые имеют в них \ *, являются регулярными выражениями. – Anonymous
Нет, этот вопрос не имеет отношения к регулярным выражениям. Контекстно-свободные грамматики указывают языки, которые не могут быть описаны регулярными выражениями.
Здесь A не является терминалом; то есть это символ, который должен быть расширен с помощью правила производства. Учитывая, что у вас есть только одно правило, это также ваш начальный символ - любая постановка в этой грамматике должна начинаться с A.
Правило производства
(1) A -> aA*b |
(2) empty_string
a и b терминальные символы - они находятся в алфавите языка, и не может быть расширен. Когда у вас больше нет нетерминалов с левой стороны, все готово.
Так что этот язык указывает слова, которые, как сбалансированные скобки, за исключением a и b вместо ( и ).
Например, вы могли бы производить ab следующим образом:
A -> aA*b (using 1)
aAb -> ab (using 2)
Кроме того, вы могли бы производить aabb:
A -> aA*b (1)
aAb -> aaA*bb (1)
aaAbb -> aabb (2)
Или даже aababb:
A -> aA*b
aA*b -> aabA*b:
aaba*b -> aababA*b:
aababA*b: -> aababb
Получить его? Звездный символ может быть немного запутанным, потому что вы видели его в регулярных выражениях, но на самом деле он делает то же самое здесь, что и там. Он называется закрытием Kleene и представляет собой все слова, которые вы можете сделать с 0 или более A с.
Регулярные выражения генерируют регулярные языки и могут обрабатываться государственными машинами.
BNF грамматики бесконтекстная грамматик, которые генерируют контекстно-свободных языков и может быть разобрана с Push Down автоматных (стек машин)
бесконтекстная грамматик может сделать все Regular грамматик может и больше.
@ danben: Только люди, более заинтересованные в рейтинговых играх, чем решения. – Anonymous