Can Non-Linear Grammars generate Regular Language?

Question

I stumbled upon the following non-linear grammar

$$S \to AB$$ $$A\to aaA\mid \epsilon$$ $$B \to Bb\mid \epsilon$$

and the language generated by this non-linear grammar is {a^2nb^m : n ≥ 0, m ≥ 0} which looks to be regular. I was successful in drawing a DFA for this language.

Thus far, I have studied that Left Linear and Right Linear grammars classify as Regular Grammar and generate Regular Languages. I know there are certain Linear Grammars that can be converted to corresponding Left Linear or Right Linear equivalent forms. Similarly, I am guessing, we can write a Right or Left Linear grammar in a Non-Linear fashion and get the same regular language which is what is happening here.

Thus, what I understand is that Left Linear or Right Linear Grammars always generate Regular languages but a Non-Linear grammar may or may not generate a regular language. Is that the correct way to put it? Are there any gaps in my understanding?

Wkipedia states "an example of a linear, non-regular language is {a^nb^n}". Can I then say that above language is an example of non-linear, regular language? That sounds and probably is wrong.

Answer 1

You are confused a bit I believe by using the terms grammar and language somewhat interchangeably.

A grammar is a set of production rules. A language is a set of words. A language is described, or generated by a grammar.

They are not the same and you should be careful at all times to see which is which.

There are a lot of terms such as "context-free", "linear", "regular", etc, that are direct properties of grammars. That is their original definition.

These terms when applied to a language, has a different, indirect meaning. When I say that a language L is X for those above properties, I mean that there exists a grammar with property X that generates L.

Now this can get confusing. Let's take your original grammar. It itself is not linear or regular, but the language it generates is both. Why? Because I can construct another grammar for it which generates the same language, which has those properties:

$$S \to A$$ $$A \to aaA \mid B$$ $$B \to bB \mid \epsilon$$

If you want to be even stricter I could make it a strictly right-linear grammar without epsilon productions (other than the whole language being nullable):

$$S \to aA_2 \mid bB \mid \epsilon$$ $$A_1 \to a A_2$$ $$A_2 \to aA_1 \mid aB \mid a$$ $$B \to bB \mid b$$

Finally, we have that for language classification we have (among others):

$$\text{Left-linear} = \text{Right-linear} =\text{Regular} \in \text{Linear} \in \text{Context-Free}$$

Can I then say that above language is an example of non-linear, regular language?

That is indeed wrong, because the language above is linear. You are confused because you are looking at the grammar, which isn't linear. Just because a certain grammar for a language isn't property X doesn't mean that there doesn't exist another grammar that generates the same language that has property X.

That's why it's generally hard to prove that a language doesn't have some property X. You need to show that every possible grammar you can construct for that language doesn't have that property, because a single one is enough to give that property to the language.