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

2 Answers 2

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$ Commented May 6, 2014 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$ Commented May 6, 2014 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$ Commented May 6, 2014 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
    Commented May 5, 2014 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$ Commented May 5, 2014 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$ Commented May 5, 2014 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
    Commented May 5, 2014 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.