The Gateway to Computer Science Excellence
+4 votes
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\}$
in Theory of Computation by Veteran (425k points)
edited by | 2k views
0
C?

3 Answers

+14 votes
Best answer

Answer : 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 by
0
this answer in detailed and should be selected as best
+9 votes
$\{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
0 votes
ans (C)
by Junior (581 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,601 answers
195,852 comments
102,216 users