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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ Because that is how it is defined. S can be any number of a's and b's in any order $\endgroup$
    – TacoB0t
    Commented Sep 25, 2017 at 18:55
  • 1
    $\begingroup$ Not in any order, an arbitrary number of a's, then an arbitrary number of b's $\endgroup$
    – lPlant
    Commented Sep 25, 2017 at 19:41
  • $\begingroup$ @iPlant Correct. My mistake $\endgroup$
    – TacoB0t
    Commented Sep 25, 2017 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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Sep 25, 2017 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
    Commented Sep 27, 2017 at 14:00

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.