CODEWITHSUNDEEP
regular-languageformal-languages
doniyor
doniyor

Reputation: 37856

how can i see directly that a language is not regular

given L={a^n b^n c^n}, how can i say directly without looking at production rules that this language is not regular? i can use pumping lemma but some guys are saying just looking at the grammar that this is not regular one. how is it possible?

Upvotes: 0

Views: 218

Answers (1)

Zagorax
Zagorax

Reputation: 11890

You have three chars in your alphabet. All of them depends on the same variable: n. Now, if you have only two of them, imagine {a^n b^n} you can easily accomplish the task with this production:

S -> ab | aSb

But you have three of them and there's no way to link all of them to the same variable. You should use two syntax category, but since you do it, they are unlinked and you can generate different string from each one of them. The only way to link them is with only one syntax category, and that is impossible.

You can't do:

S -> abc | aSbc

In fact, you can't have a syntax category in your final string, so that is not a string. It needs to be transformed again. And what can you do from that point? You can do:

aabcbc

or you can do:

aaSbcbc

The first one is a string, and isn't part of your language. The second is not a string, yet. But it's very easy to see that you can't manage to do any allowed string from that.

Upvotes: 1

Related Questions