1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ A linear language is one which can be generated using a linear grammar. All regular languages are linear. $\endgroup$ – Yuval Filmus Jan 5 at 17:21
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Noted. Let me state my updated understanding of this: When we say that a 'language' is linear, we mean to say there there exists some linear grammar for it. Then, only time a language can be termed non-linear is when there no linear grammar for it. $\endgroup$ – Vaibhav Raj Singh Jan 5 at 18:33
  • $\begingroup$ @VaibhavRajSingh Correct. Note that that can be very hard to prove. $\endgroup$ – orlp Jan 5 at 21:26

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.