I have these two languages

$L={\{a^n b^m,n≥m+5,m>0}\}$ Where $∑=(a,b)$

$L={\{a^n b^m,n≥m+5,m≤5}\}$ Where $∑=(a,b)$

As you can see that there is only one difference, the condition of m is different.

What my question is that, are these languages regular or non-regular?

If these both languages are non-regular then how can we able to prove that using pumping lemma?



  • Split $a^n$ into $\color{blue}{a^n}$ and $\color{green}{a^5}$, that is, consider language $$L = \{\color{blue}{a^n}\color{green}{a^5}b^m \mid \color{blue}{n}\geq m, m > 0\},$$ where the two new letters $\color{blue}{a}$ and $\color{green}{a}$ are just two distinguishable letters $a$, and $\color{blue}{n} = n-5$.
  • For the second language observe that \begin{align}\{a^nb^m\mid n\geq m+5, m\leq 5\} &= \bigcup_{i=0}^{5}\ \{a^nb^m\mid n\geq m+5, m=i\} \\ &=\bigcup_{i=0}^{5}\ \{a^nb^i\mid n\geq i+5\}\\ &=\{a^{\color{blue}{n}}a^5b^0\mid \color{blue}{n}\geq 0\} \cup \ldots \cup \{a^{\color{blue}{n}}a^{10}b^5\mid \color{blue}{n}\geq 0\}.\end{align}

I hope this helps $\ddot\smile$

  • $\begingroup$ you are saying that both the languages are non-regular? $\endgroup$ – Aniq Mar 28 '15 at 12:00
  • $\begingroup$ In first language, how to choose Pumping length? $\endgroup$ – Aniq Mar 28 '15 at 12:01
  • $\begingroup$ What will be win first language? I think it will be a^p a^5 b^p $\endgroup$ – Aniq Mar 28 '15 at 14:20
  • $\begingroup$ @Aniq Suppose that there is an automaton with $k$ states that recognizes $L$, consider the word $a^{k+1}a^5b^{k+1}$. Because the automaton has $k < k+1$ states, then when parsing $b$'s some state has to happen at least twice. That means that there is a loop and you can use it any number of turns you want, so for any number $x$ there is $y > x$ such that your automaton accepts $a^{k+1}a^5b^{y}$. Surely you can find $y$ so that that word shouldn't be in $L$. $\endgroup$ – dtldarek Mar 28 '15 at 15:22
  • $\begingroup$ @Aniq Going back to the pumping lemma, your subword $w$ should be $b^p$, with $uwv = a^pa^5b^p$ (see here). $\endgroup$ – dtldarek Mar 28 '15 at 15:24

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.