search
Log In
12 votes
3.9k 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
edited by
3.9k views
0
C?

3 Answers

28 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.  


selected by
0
this answer in detailed and should be selected as best
16 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.

edited by
0 votes
ans (C)
Answer:

Related questions

13 votes
4 answers
1
4.6k views
If $L$ is a regular language over $\Sigma = \{a,b\} $, which one of the following languages is NOT regular? $L.L^R = \{xy \mid x \in L , y^R \in L\}$ $\{ww^R \mid w \in L \}$ $\text{Prefix } (L) = \{x \in \Sigma^* \mid \exists y \in \Sigma^* $such that$ \ xy \in L\}$ $\text{Suffix }(L) = \{y \in \Sigma^* \mid \exists x \in \Sigma^* $such that$ \ xy \in L\}$
asked Feb 7, 2019 in Theory of Computation Arjun 4.6k views
22 votes
6 answers
2
10.3k views
For $\Sigma = \{a ,b \}$, let us consider the regular language $L=\{x \mid x = a^{2+3k} \text{ or } x=b^{10+12k}, k \geq 0\}$. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for $L$ ? $3$ $5$ $9$ $24$
asked Feb 7, 2019 in Theory of Computation Arjun 10.3k views
21 votes
3 answers
3
4.1k views
Consider the following sets: S1: Set of all recursively enumerable languages over the alphabet $\{0, 1\}$ S2: Set of all syntactically valid C programs S3: Set of all languages over the alphabet $\{0,1\}$ S4: Set of all non-regular languages over the alphabet $\{ 0,1 \}$ Which of the above sets are uncountable? S1 and S2 S3 and S4 S2 and S3 S1 and S4
asked Feb 7, 2019 in Theory of Computation Arjun 4.1k views
19 votes
3 answers
4
6.4k views
Let $\Sigma$ be the set of all bijections from $\{1, \dots , 5\}$ to $\{1, \dots , 5 \}$, where $id$ denotes the identity function, i.e. $id(j)=j, \forall j$. Let $\circ$ ... $L=\{x \in \Sigma^* \mid \pi (x) =id\}$. The minimum number of states in any DFA accepting $L$ is _______
asked Feb 7, 2019 in Theory of Computation Arjun 6.4k views
...