The following is a screenshot of a lecture slide from my programming language concepts course:
According to Wikipedia and other sources, a regular grammar is one that is either left linear or right linear, meaning it has at most:
- one nonterminal symbol on the left end of its right hand side
e.g., A -> Ba
- one nonterminal symbol on the right end of its right hand side
e.g., A -> aB
But if we follow this definition, then the "regular grammar" in the screenshot above isn't really a regular grammar because it has two nonterminal symbols on its right hand sides.
My teacher argues it "technically" is because:
Identifier -> Identifier Letter
is "essentially" the same as writing multiple things like:
Identifier -> Identifier 'a'
Identifier -> Identifier 'b'
...
More generally, my instructor says that if a grammar's production rules can be reduced to a form where they have at most one nonterminal symbol, then that grammar is regular. To me, this doesn't seem correct—because then essentially, just by substitution, we can reduce any grammar we want to a regular form. And it seems to destroy the definition/restriction imposed on regular grammars, which is that they may have at most one nonterminal.
Could someone please clarify whether this is in fact a valid regular grammar?
Identifier
is a nonterminal symbol, andLetter
is a nonterminal symbol, thenIdentifier → Identifier Letter
has two nonterminal symbols on the right hand side. $\endgroup$Identifier → Identifier
andIdentifier → Letter
separately, and then execute those production rules one after another to achieve the same result? $\endgroup$