I'd agree that they're equivalent, since the end result of both is one or more <bar>
's. But if any new rules were added to <foo>
(such rules involving terminals or non-terminals other than <bar>
), they probably wouldn't be equivalent anymore.
Are these two context free grammar rules the same?
-
01-07-2022 - |
Question
Is there a difference between these two grammar definitions (where |
denotes OR and ;
is just a regular character)?
1. <foo> ::= <bar> | <foo> ; <bar>
2. <foo> ::= <bar> | <bar> ; <foo>
It seems to me that foo would match a sequence that looks like <bar> ; <bar> ; <bar> ; ....
regardless of which definition is used. Am I missing something here or are they functionally the same?
Solution
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow