0
$\begingroup$

Let $L$ be a language defined over $\Sigma = \left \{ a, b \right \}$ such that $L = \left \{ x\#y \mid x,y \in \Sigma^*, \# \text { is a constant and } x \neq y \right \}$ State whether the language L is a CFL or not? Give valid reasons for the same.


Now, I think that the given language is not a CFL. I have used the pumping lemma test for showing that L is not CFL. Specifically, I have done the following-

Consider a string $w = abb\#aab$. Obviously, $w \in L$.

Let, $u = \epsilon \\ v = a \\ w = bb\#aa \\ x = b \\ y = \epsilon$

Here, $|vx| \geq 1$

But, $uv^2wx^2y = aabb\#aabb \notin L$ Therefore, pumping lemma test result is negative. Therefore, we can conclude that the given language is not a CFL.

Now, I have a doubt regarding the above method- I know that given a CFL, if we want to perform the pumping lemma test for the CFL, we must always use strings which are of length greater than or equal to the minimum pumping length. In fact, this also confirms to the condition that the length of the string $w$ used for the pumping lemma test (denoted by $|w|$) must be greater than or equal to n.

Therefore, when I use $w = abb\#aab$ for doing the pumping lemma test, I implicitly make the assumption that 7 is greater than or equal to the minimum pumping length (if $L$ were to be a CFL). Am I correct or incorrect in doing so?

$\endgroup$
0
$\begingroup$

The language is context-free.

The statemant of the pumping lemma claims "there exists a $uvwxy$-division", so in order to show a language non-context-free, you have to check that every possible division leads to a pumping contradiction. Your mistake is that you only checked one division.

$\endgroup$

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.