Answer : C
Detailed Video Solution with Complete Analysis & Variations: https://www.youtube.com/watch?v=ZSGsmg_9X4o&t=5744s
Input alphabet $\Sigma = \{ a,b\}$
A.
$\{ww^R| w \in \{ a,b\}^*\}$
This language is well-known CFL. The CFG generating this language is as following :
$G_1 : S \rightarrow aSa|bSb| \in$
B.
$\{wa^nb^nw^R| w \in \{ a,b\}^*, n\geq 0\}$
This language is also CFL and can easily be generated by a slight modification in the above Grammar $G_1$. The CFG generating this language is as following :
$G_2 : S \rightarrow aSa|bSb| \in | A$
$\,\,\,\,\,\,\,\,\,\,\,A \rightarrow aAb | \in$
D.
$\{a^nb^i| i \in \{ n,3n,5n\}^, n\geq 0\}$
This language is also CFL. It can be seen as Union of Three CFLs $a^nb^n,a^nb^{3n}, a^nb^{5n}.$. The CFG generating this language is as following :
$G : S \rightarrow A|B|C $
$\,\,\,\,\,\,\,\,\,\,\,A \rightarrow aAb | \in$
$\,\,\,\,\,\,\,\,\,\,\,B \rightarrow aBbbb | \in$
$\,\,\,\,\,\,\,\,\,\,\,C \rightarrow aCbbbbb | \in$
So, By now, you could get the answer to be the Third Option i.e. $C$ Or we can use Pumping lemma to show that It is Non-CFL.
C.
$L = \{wa^nw^Rb^n| w \in \{ a,b\}^*, n\geq 0\}$
$L$ is a Non-CFL.
We can use "Pumping lemma for CFL" to prove that $L$ is Not a CFL.
Pumping lemma for CFLs:
Let $L$ be a CFL. Then there exists some integer constant $P \geq 1$ (Called Pumping length or pumping-lemma constant) such that if $w ∈ L$ with $|w| ≥ P,$ then we can write $w = uvxyz,$ subject to the following conditions:
1. $|vxy| ≤ P.$
2. $vy \neq \in .$
3. For all $i ≥ 0,$ we have $uv^ixy^iz ∈ L.$
i.e. Informally, For every sufficiently large string $w$ in $L,$ We must be able to split it such that it is possible to find at most two short, nearby substrings that we can “pump” $i$ times in tandem, for any non-negative integer $i,$ and the resulting string will still be in that language.
Now, Assume that Given $L$ is CFL, Hence, It will satisfy Pumping lemma for CFL.
So, There must be some integer constant (pumping length) $\geq1$ exists for this language. Let it be $P.$
So, Now for every string $w \in L$ whose length is greater than or equal to $P,$ we must have some partition $uvxyz$ satisfying all the above conditions.
So, Let me take the string $b^{2P} a^{2P}b^{2P}b^{2P}$, Now Try to split it into five parts $uvxyz$ such that All the Three conditions of pumping lemma must satisfy.
Basically in Pumping lemma for CFL, You want to find $"$at most $P"$ consecutive symbols in the String(anywhere in the String) such that you can find two short sub-strings in that part and Pump those sub-strings in tandem.
But for the above String $b^{2P} a^{2P}b^{2P}b^{2P}$, we cannot find any such at most $P$ consecutive symbols anywhere in the string which will satisfy the Pumping lemma conditions. (Hint : Take Those at most $P$ consecutive symbols in the first part of the string i.e. $b^{2P}$ or in the second part i.e. $a^{2P} $ or in third part or in fourth part or between the parts etc.. covering all possible partitions.. )
So, Given language doesn't satisfy Pumping lemma and hence, $L$ is Not CFL.
The informal/intuitive idea for Non-CFLness of $L$ (language in Option $C$) is that You need PDA to do the reverse matching i.e. $w \,\,\,matched\,\,\,with\,\,\,w^R$ But Because $a^n$ is in between $w\,\,and\,\,w^R$ and $b^n$ is after $w^R$, You can either match $ww^R$ or you can match $a^nb^n$ but Not both simultaneously. This is Informal Idea and by practice It becomes easier to check for a language being CFL or Not using this informal method.
Detailed Video Solution with Complete Analysis & Variations: https://www.youtube.com/watch?v=ZSGsmg_9X4o&t=5744s
