0
$\begingroup$

In short, is this similar to how $a^nb^n$ is not a regular langauge?

$L$ = {$ { a^nsb^n : s \in L(a^*b^*) ,\ n \ge 1 } $}

For instance, if we have the string $w=a^psb^p$, and we know that $|xy| \le p$, there would simply be a disproportianate amount of a's or b's regardless of where we put $y$ ?

$\endgroup$
1
$\begingroup$

Your language is equal to $L(a^+b^+)$ (why?).

$\endgroup$
  • $\begingroup$ Because that is how it is defined. S can be any number of a's and b's in any order $\endgroup$ – TacoB0t Sep 25 '17 at 18:55
  • 1
    $\begingroup$ Not in any order, an arbitrary number of a's, then an arbitrary number of b's $\endgroup$ – lPlant Sep 25 '17 at 19:41
  • $\begingroup$ @iPlant Correct. My mistake $\endgroup$ – TacoB0t Sep 25 '17 at 21:08
1
$\begingroup$

You cant use the pumping lemma to show that a language is regular, you can only show that if the lemma fails, then it is not regular. As an aside, the language you gave is regular, and as Yuval has said it is $L(a^+b^+)$, another way to look at $L(a^+b^+)$ is $L(a^1a^*b^*b^1)$ a DFA is the easiest way to show this one.

$\endgroup$
  • $\begingroup$ Right, I meant that I want to prove that it is NOT a regular language. My confusion of this lies in the intuitive understanding that we just can't keep track of how many a's or b's we have in a finite state, correct? But it wouldn't matter because s will addan arbitray amount of either? $\endgroup$ – TacoB0t Sep 25 '17 at 21:10
  • $\begingroup$ we dont need to keep track, as long as there is at least one a and one b we can always say that the rest of the a's and b's are a part of s and that $n=1$. The $n$ is the trick in this language. Even if $n$ is something higher like $n=100$ we can still parse the string so that $n=1$. Take $w=a^{50} s b^{50}$ let $s_2$ = $a^{49} s b^{49}$, $s_2 \in a^* b^*$ so $w = a^1 a^{49} s b^{49}b^1 = a^1 s_2 b^1$ $\endgroup$ – lPlant Sep 27 '17 at 14:00

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.