patternMinor
This doesn't seem like a valid regular grammar; my instructor says it is
Viewed 0 times
thisseemregularlikedoesngrammarvalidsaysinstructor
Problem
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:
e.g., A -> Ba
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?
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?
Solution
Your teacher is wrong, unless of course s/he does not adhere to the wikipedia definitions. It is "technically" equivalent to a regular grammar, but that is not a well defined concept. What can we allow as extensions that give us "technically" regular grammars.
There is a concept that is perhaps suited. That is self-embedding. A variable $A$ is self-embedding if $A\Rightarrow^*uAv$ for non-empty $u,v$. A grammar is non self-embedding if none of its variables is self-embedding. Every non self-embedding context-free grammar has an equivalent regular grammar, which was already observed by Chomsky. With this concept we extend the regular grammars, while we are certain to stay within the regular languages.
And, since you are asking more details, your instructor is wrong again on the single nonterminal remark. Such grammars also include $S\to aSb\mid \varepsilon$ for which every sentential form has (at most) one nonterminal, but for which the language is non-regular. In fact these languages are called linear, and form a family between regular and context-free.
Note that $S\to AB, A\to aA|\varepsilon, B\to Bb|\varepsilon$ defines a regular language (mixing leftmost and rightmost). On the other hand $A\to aB\mid\varepsilon, B\to Ab$ is nonregular. This exemplifies the non self-embedding distinction.
There is a concept that is perhaps suited. That is self-embedding. A variable $A$ is self-embedding if $A\Rightarrow^*uAv$ for non-empty $u,v$. A grammar is non self-embedding if none of its variables is self-embedding. Every non self-embedding context-free grammar has an equivalent regular grammar, which was already observed by Chomsky. With this concept we extend the regular grammars, while we are certain to stay within the regular languages.
And, since you are asking more details, your instructor is wrong again on the single nonterminal remark. Such grammars also include $S\to aSb\mid \varepsilon$ for which every sentential form has (at most) one nonterminal, but for which the language is non-regular. In fact these languages are called linear, and form a family between regular and context-free.
Note that $S\to AB, A\to aA|\varepsilon, B\to Bb|\varepsilon$ defines a regular language (mixing leftmost and rightmost). On the other hand $A\to aB\mid\varepsilon, B\to Ab$ is nonregular. This exemplifies the non self-embedding distinction.
Context
StackExchange Computer Science Q#92638, answer score: 3
Revisions (0)
No revisions yet.