1
$\begingroup$

In the answer to this question, I'm not understanding how the string is derived for a given $l$.

For example,

Case 1: $vx = a^i$ where $i > 0$. Choose $l = 2$ to get $a^{n+i} b^{n+1} c^{n+1} d^n \notin L$.

Why is $l = 2$ chosen and how is $a^{n+i}b^{n+1}c^{n+1}d^n$ derived from $l = 2$?

Also, how can $vx$ be chosen instead of $vwx$ as the OP chose? What do we do about $w$? Is it the empty string?

$\endgroup$

1 Answer 1

2
$\begingroup$

The essential idea is that pumping lemma tells you about string $uv^lwx^ly$ with $l \geq 0$. That is, you can "pump" to $uwy$, if $l = 0$, that way shortening the initial string.

The answer considers the string $a^n b^{n+1} c^{n+1} d^n$. Removing a single $b$ or inserting a single $a$ would move the string out of the language. Removal and insertion correspond to $l = 0$ and $l = 2$.

The answer only considers $vx$, because $w$ does not matter - it will not be pumped.

If $v$ or $x$ contains any $a$s, double them to get more $a$s then $c$s. If $v$ or $x$ contains any $b$s, remove them to get fewer $b$s than $d$s. $v$ and $x$ will never contain both $a$s and $c$s, because $|vwx| \leq n$. Same is true about the other pair of symbols.

$\endgroup$

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.