# Is $a^n b^m$ never regular if n and m have some relation between them?

I know what regular and context free language are and how regular language needs finite memory and other stuff.

What concerns me is that I think if $a^nb^m$ such that $n$ and $m$ have some relation between them then they can not be regular. But I can't find any such thing written anywhere. Am I correct to state so?

• Hint: Is $a^nb^n$ regular or not regular? Why is that? And if $a^nb^n$ is not regular, what do you suspect $a^nb^m$ is? I am assuming that by relation between them you mean for example that $n$ is greater than $m$, or that $m$ is greater than or equal to $n$, and so on. May 5 '14 at 11:09
• i know a^n b^n is not regular.We have to count numbers of a's and b's for that .we need stack .hence context free."relation between them you mean for example that n is greater than m, or that m is greater than or equal to n, and so on"...yes i mean that .here also n =m is a relation hence not regular. thats my point May 5 '14 at 11:11
• So if you have a language that satisfies the description of you language, and it is not regular, what does that say about your language in more general terms? If $a^nb^m, n = m$, is not regular, does that say anything about your language $L$ with any kind of binary relation $R$? May 5 '14 at 11:25
• You should carefully define what you mean by "have some relation between them" since $\{a^nb^m \mid n \equiv m\pmod{15}\}$ is regular, for instance. May 5 '14 at 12:38
• @sandeepbisht. The language $\{a^nb^n\mid n<15\}$ is finite, hence regular. May 6 '14 at 12:37

For a relation $R(n,m)$, let $L_R = \{ a^n b^m : R(n,m) \}$. Call a relation residual if for some $k \geq 1$ and for some $A \subseteq [k]^2$, $$R(n,m) \Leftrightarrow (n,m) \pmod{k} \in A.$$ Call a relation semi-residual if it differs from a residual relation by a finite number of points.

Claim: $L_R$ is regular iff $R$ is semi-residual.

Proof: It is not hard to check that if $R$ is semi-residual then $L_R$ is regular. For the other direction, consider an automaton for $L_R$. For each state $\sigma$, let $L_\sigma$ be the set of all $n$ such that upon reading $a^n$, the automaton reaches $\sigma$. Since $L_\sigma$ is unary, it is eventually periodic. By taking the least common multiple of all periods, we see that the state that for $n \geq n_0$, the automaton find itself upon reading $a^n$ depends only on $n\pmod{k_a}$ from some $k_a$. Doing the same for $b^m$, we see that for $n \in L_\sigma$, the set of all $m$ such that $a^n b^m \in L$ is eventually periodic, and so for $m \geq m_0$, depends only on $\sigma$ and on $m\pmod{k_b}$ for some $k_b$. Taking $k$ to be the LCM of $k_a,k_b$, we find that for $n \geq n_0, m \geq m_0$, $a^n b^m \in L$ depends only on $(n,m) \pmod{k}$. Hence the corresponding $R$ is semi-residual.

• can we say LR is not regular if R is not semi-residual ? May 6 '14 at 4:23
• @sandeepbisht If you believe my claim, then it implies that $L_R$ is not regular if $R$ is not semi-residual. Perhaps you want to look up the meaning of iff (if and only if). May 6 '14 at 5:04
• "Call a relation residual if for some k≥1 and for some A⊆[k]2". why [k]^2 why not 2^k ? May 6 '14 at 5:47

Let $L = \{ a, b \in \Sigma \mid a^nb^m, R(n,m) \}$. This language may be regular: if for example $R = \mathbb{N} \times \mathbb{N}$, then $L = a^*b^*$. So you can't say whether $L$ is regular or not without knowing something about $R$.

There are languages with a relation $R$ that are not regular; for example $L = a^nb^n$.

• It should be possible to get an intuition about allowable $R$ from Myhill-Nerode.
– Raphael
May 5 '14 at 12:50
• Another example when $L$ is regular is when $R(n,m)$ states that $n,m$ have the same parity. Using Myhill–Nerode, one should be able to come up with a complete list of all $R(n,m)$ for which $L$ is regular. May 5 '14 at 14:31
• @Raphael Intuition, possibly. Are you aware of anything we can say formally about the connection between properties of $R$ and the regularity of $L$? May 5 '14 at 14:34
• @C.Brand I would guess that $R$ has to have finitely many "equivalence" classes. I'm not sure whether that's sufficient.
– Raphael
May 5 '14 at 14:47