1
$\begingroup$

The language on the alphabet $\{a,b\}$ is $$L=\{ab^nab^{n+1} |n>0\}$$

so i have to take a string w = xyz:

what's the best string to choose such that $|w| > n$? and then what about the division?

like $ w=ab^nab^{n+1}$ is a correct option? Then how can I divide this into three pieces? My attempt:

$ x = ab^s $ with $ 0 ≤ s ≤ n -1 $

$ y= b^ta $ with $ 0 < t ≤ n - t $

$ z = b^k $ with $ 0 ≤ k < n - t - s $

$\endgroup$
  • 1
    $\begingroup$ You don't get to choose how to divide the string! You have to consider all possible divisions. $\endgroup$ – Yuval Filmus Jan 25 '17 at 21:10
  • $\begingroup$ Yes but I can choose the string to divide, important is that it still belongs to the languages and that it is $ > n $. Right? $\endgroup$ – emaph Jan 25 '17 at 21:15
  • $\begingroup$ You really don't have much choice regarding the string $w$. It will have to be $ab^nab^{n+1}$ for large enough $n$. $\endgroup$ – Yuval Filmus Jan 25 '17 at 21:17
  • $\begingroup$ Ok I got this. Then what about the division? $\endgroup$ – emaph Jan 25 '17 at 21:29
  • $\begingroup$ What about it? You have to consider all possible ways. I suggest taking a look at some worked-out examples. You can find many on the web. If you're still lost after that, I suggest asking your TA. $\endgroup$ – Yuval Filmus Jan 25 '17 at 21:30
0
$\begingroup$

w = abn-1abn.

We have to consider all the division xyz = w with |y| >= 1 and |xy| <= n. So

x = apbr

y = aqbs

z = btabn

where:

  • p + q = 1
  • r > 0 implies p = 1
  • q + s > 0
  • r + s + t = n - 1

Let's now consider w' = xy0z=apbr+tabn. If x is the empty string, then w' is missing the initial 'a' (and maybe some b), so w' is not in L. Else if x is not empty, we know that y contains at least one occurrence of 'b', so w' can't be in the form abnabn+1 and w' is not in L.

$\endgroup$
  • $\begingroup$ I got your process, even if probably I would have never managed to think about this solution. Thanks! $\endgroup$ – emaph Jan 26 '17 at 18:46

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.