2
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$ May 5 '14 at 11:09
  • $\begingroup$ 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 $\endgroup$ May 5 '14 at 11:11
  • $\begingroup$ 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$? $\endgroup$ May 5 '14 at 11:25
  • 5
    $\begingroup$ 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. $\endgroup$ May 5 '14 at 12:38
  • 1
    $\begingroup$ @sandeepbisht. The language $\{a^nb^n\mid n<15\}$ is finite, hence regular. $\endgroup$ May 6 '14 at 12:37
5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ can we say LR is not regular if R is not semi-residual ? $\endgroup$ May 6 '14 at 4:23
  • $\begingroup$ @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). $\endgroup$ May 6 '14 at 5:04
  • $\begingroup$ "Call a relation residual if for some k≥1 and for some A⊆[k]2". why [k]^2 why not 2^k ? $\endgroup$ May 6 '14 at 5:47
4
$\begingroup$

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$.

$\endgroup$
4
  • 1
    $\begingroup$ It should be possible to get an intuition about allowable $R$ from Myhill-Nerode. $\endgroup$
    – Raphael
    May 5 '14 at 12:50
  • 1
    $\begingroup$ 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. $\endgroup$ May 5 '14 at 14:31
  • $\begingroup$ @Raphael Intuition, possibly. Are you aware of anything we can say formally about the connection between properties of $R$ and the regularity of $L$? $\endgroup$ May 5 '14 at 14:34
  • $\begingroup$ @C.Brand I would guess that $R$ has to have finitely many "equivalence" classes. I'm not sure whether that's sufficient. $\endgroup$
    – Raphael
    May 5 '14 at 14:47

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.