2k views

Which one of the following languages over $\Sigma=\{a, b\}$ is NOT context-free?

1. $\{ww^R \mid w \in \{a, b\}^*\}$
2. $\{wa^nb^nw^R \mid w \in \{a,b\}^*, n \geq 0\}$
3. $\{wa^nw^Rb^n \mid w \in \{a,b\}^* , n \geq 0\}$
4. $\{ a^nb^i \mid i \in \{n, 3n, 5n\}, n \geq 0\}$

edited | 2k views
0
C?

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.

by Boss (26.5k points)
selected
0
this answer in detailed and should be selected as best
$\{ww^r \} \rightarrow$ well known CFL.

$\{ wa^n b^n w^r \} \rightarrow$ inside out comparison. PDA can do this.

$\{ a^n b^i, \: i=n, \: 3n,\: 5n\} \rightarrow$ is CFL

$\{wa^n w^r b^n \} \rightarrow$ Alternate comparison. PDA can not do this.
by Veteran (60.6k points)
edited by