My understanding is that a machine with finite states cannot keep track of the n's being the same in $L$ = {$ { a^nsb^n : s \in L(a^*b^*) ,\ n \ge 1 } $}, similar to the case with how $a^nb^n$ is not a regular language. For instance, if we take a string $aaaa ab bb$, where the fifth a and the following b are $s$, how is this valid? We have a disproportionate amount of a's to b's. Using the pumping lemma, I feel that this is disproven easily if $y$ (from $xyz$ division) is any number of a's at the beginning.

If this can be proven using a DFA, what is it?


marked as duplicate by fade2black, Yuval Filmus, Evil, Rick Decker, Thomas Klimpel Oct 10 '17 at 20:54

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


You don't need to "keep track of $n$ being the same." Another way to write the language is

$$L = \{a^na^ib^jb^n\mid n\geq 1,\ i,j\geq 0\}=\{a^{n+i}b^{j+n}\mid n\geq 1,\ i,j\geq 0\}\,.$$

So, now, given a string $a^sb^t$, you just need to decide if you can choose $n\geq1$ and $i,j\geq 0$ such that $s=n+i$ and $t=n+j$. If so, then $a^sb^t\in L$; otherwise, $a^sb^t\notin L$. If $s=0$ or $t=0$, we can't choose $n$, $i$ and $j$ as required, since $n\geq 1$. However, as long as $s>0$ and $t>0$, we can take $n=1$, $i=s-1$ and $j=t-1$. Therefore,

$$L = \{a^sb^t\mid s,t\geq 1\}\,,$$

which is the language matched by the regular expression $aa^*b^*b$.

  • 1
    $\begingroup$ Oooooohhh I see. This clears everything up for me. Thanks David! $\endgroup$ – TacoB0t Sep 25 '17 at 23:10
  • $\begingroup$ This question has already been asked and answered here. $\endgroup$ – fade2black Sep 26 '17 at 7:41

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