6
$\begingroup$

Is it true that the set $\{ 0^{n^2} \mid n \in\mathbb{N} \}$ is not regular because it does not grow linearly?

Regular sets are called regular because if you have a regular set then you can always pump it up (pumping lemma) in regular intervals and get other things in the set. They string out at very linear intervals. That's why anything that grows in other than linear intervals is not regular.

Therefore, $\{ a^{n^2} b^n \mid n \in\mathbb{N} \}$ is not regular, right? Also, I know that $\{ a^n b^n \mid n \in\mathbb{N} \}$ is not regular, but what about $\{ a^{cn} b^{dn} \mid n \in\mathbb{N} \}$ for any integer coefficients $c$ and $d$?

$\endgroup$
  • $\begingroup$ By the way: Is there a reason that you didn't ask the last part (about $a^{cn}b^{dn}$) as a separate question? It doesn't seem to be connected to the rest of the post. $\endgroup$ – sepp2k Apr 3 '12 at 18:13
  • 1
    $\begingroup$ Is this a homework? If it is please add the homework tag to the question. $\endgroup$ – Kaveh Apr 3 '12 at 19:54
  • 1
    $\begingroup$ What does "very linear intervals" mean? $\endgroup$ – Raphael Apr 3 '12 at 20:57
5
$\begingroup$

Is it true that the set $0^{n^2}$ is not regular because it does not grow linearly?

Yes, that's true. That follows from the pumping lemma as explained in the paragraph you quoted.

Therefore, $a^{n^2} b^n$ ... is not regular?

Yes, that's also true for the same reason.

Also, I know that $a^n b^n$ is not regular, but what about $a^{cn} b^{dn}$ for any integer coefficients $c$ and $d$?

The language $\left\{a^{cn} b^{dn} \mid n \in \mathbb{N}\right\}$ where $c$ and $d$ are fixed is regular if and only if $c$ or $d$ is equal to 0.

$\endgroup$
  • $\begingroup$ So that means a^2n b^n is not regular, right? $\endgroup$ – Lexy Yang Apr 3 '12 at 18:06
  • $\begingroup$ @LexyYang Right. $\endgroup$ – sepp2k Apr 3 '12 at 18:08

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.