patternMinor
Regular sets have linear growth?
Viewed 0 times
linearregulargrowthsetshave
Problem
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$?
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$?
Solution
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.
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.
Context
StackExchange Computer Science Q#1006, answer score: 5
Revisions (0)
No revisions yet.