1
$\begingroup$

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... enter image description here

$\endgroup$
  • 2
    $\begingroup$ What are the two languages you are supposedly concatenating to obtain $L$? $\endgroup$ – dkaeae Feb 27 '19 at 13:50
  • 2
    $\begingroup$ Why don't you include the link to what you're quoting for context? $\endgroup$ – Daniel McLaury Feb 27 '19 at 14:02
  • 1
    $\begingroup$ 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? $\endgroup$ – Rick Decker Feb 27 '19 at 14:09
  • $\begingroup$ geeksforgeeks.org/… this is the link, check line number 5. $\endgroup$ – user6394019 Feb 27 '19 at 15:02
6
$\begingroup$

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.

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

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.