# Why language is not regular

Taken from site "Geeks For Geeks". The lemma: "A concatenation of pattern(regular) and a non-pattern(not-regular) is also not regular language."

example: $$\left \{L={a^{n}b^{2m}|n\geq 1,m\geq 1} \right \}$$

I think I managed to build dfa (q2 is an accepting state) for language. perhaps I'm wrong...

• What are the two languages you are supposedly concatenating to obtain $L$? – dkaeae Feb 27 '19 at 13:50
• Why don't you include the link to what you're quoting for context? – Daniel McLaury Feb 27 '19 at 14:02
• Your DFA does accept the language you call $L$, why do you think that is the concatenation of a regular and a non-regular language? – Rick Decker Feb 27 '19 at 14:09
• geeksforgeeks.org/… this is the link, check line number 5. – user6394019 Feb 27 '19 at 15:02

Yes, you are absolutely right. GeeksforGeeks is just wrong in this case.

Your analysis is correct. The language $$L=\{a^n b^{2m} \mid n \ge 1, m \ge 1\}$$ certainly is regular. Your DFA seems fine. I don't know why the GeeksforGeeks article claims it is not; but in any case they are wrong. It's a strange example; even by their own notions of what counts as a "regular pattern", $$b^{2m}$$ is a "regular pattern", so I don't know why they are giving that example.

Even if we try to look at better examples, the claim is still wrong. For instance, consider the language

$$L = \{a^n a^p \mid n \ge 0, p \text{ is prime}\}.$$

This language is described by the concatenation of a "regular pattern" and a "non-regular pattern", so that article claims it should be not regular -- but they're wrong. In fact, $$L$$ is regular, as $$L = \{a^m \mid m \ge 2\}$$.

This whole notion of a "regular pattern" and "non-regular pattern" in that article is pretty much baloney. I realize what they're trying to do -- they're trying to look for a shortcut to quickly tell whether a language is regular based on the syntax of the description of the language -- but those proposed rules are not a reliable way to tell whether a language is regular or not, and the notion of a "regular pattern" is not well-defined. That's not a standard concept -- it's just something someone on the Internet made up. At best, it is a way to form a quick guess at whether a language is regular or non-regular -- but I would recommend always following that up by proving your guess is correct, as their proposed rules are a bit dodgy.

Perhaps a lesson is to rely on primary sources, like well-regarded textbooks, and don't trust too much what you read on the Internet.

• Small change: a^n a^p = a^m: m ≥ 2. – gnasher729 Feb 27 '19 at 22:26
• @gnasher729, oh yeah -- thanks! – D.W. Feb 28 '19 at 2:52