The following is a screenshot of a lecture slide from my programming language concepts course:

enter image description here

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?

  • $\begingroup$ But if Identifier is a nonterminal symbol, and Letter is a nonterminal symbol, then Identifier → Identifier Letter has two nonterminal symbols on the right hand side. $\endgroup$
    – AleksandrH
    Jun 2 '18 at 17:08
  • $\begingroup$ @PålGD Is it because we can write Identifier → Identifier and Identifier → Letter separately, and then execute those production rules one after another to achieve the same result? $\endgroup$
    – AleksandrH
    Jun 2 '18 at 17:10
  • $\begingroup$ Hiw do you reduce a production rule containing two recursive non-terminals to a form witb one non-terminal using only substitution? (Reducing it to a new non-terminal with a non-regular production rule doesn't count, for obvious reasons). $\endgroup$
    – rici
    Jun 5 '18 at 21:35

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.

  • $\begingroup$ Hmm, but in this case it's not self embedding, just recursive. $\endgroup$
    – AleksandrH
    Jun 2 '18 at 18:33
  • 1
    $\begingroup$ It is "technically" equivalent to a regular grammar, but that is not a well defined concept. Eh yes it is? The language generated by this context-free grammar happens to be regular. $\endgroup$
    – orlp
    Jun 7 '18 at 2:53
  • $\begingroup$ @orlp You are right, my intention was to ask for a specific set of rules that defines the possible equivalence of grammars. In my opinion, just requiring "the language is regular" is not very productive as that property is undecidable for context-free grammars. $\endgroup$ Jun 7 '18 at 6:59
  • $\begingroup$ @HendrikJan I don't think it's very productive to disregard an equivalence because it's undecidable in the general case - it's perfectly decidable and useful here. $\endgroup$
    – orlp
    Jun 7 '18 at 12:05
  • $\begingroup$ @orlp Yes, this particular grammar is easily changed into a regular one. My problem is that I do not know what "technically equivalent" means? What are the rules for that? I wanted to argue that "its language is regular" is too broad to be an answer for general context-free grammars. The concept of non-self-embedding is a possible syntactic solution. $\endgroup$ Jun 11 '18 at 12:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.