0

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?

Aniq
  • 327

1 Answers1

1

Hint:

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

dtldarek
  • 37,381
  • you are saying that both the languages are non-regular? – Aniq Mar 28 '15 at 12:00
  • In first language, how to choose Pumping length? – Aniq Mar 28 '15 at 12:01
  • What will be win first language? I think it will be a^p a^5 b^p – Aniq Mar 28 '15 at 14:20
  • @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$. – dtldarek Mar 28 '15 at 15:22
  • @Aniq Going back to the pumping lemma, your subword $w$ should be $b^p$, with $uwv = a^pa^5b^p$ (see here). – dtldarek Mar 28 '15 at 15:24