# Context Free Language

 Question 1
Consider the following languages:

\begin{aligned} L_1&= \{ ww|w \in \{a,b \}^* \} \\ L_2&= \{a^nb^nc^m | m,n \geq 0 \} \\ L_3 &= \{a^mb^nc^n|m,n \geq 0 \} \end{aligned}

Which of the following statements is/are FALSE?
MSQ
 A $L_1$ is not context-free but $L_2$ and $L_3$ are deterministic context-free. B Neither $L_1$ nor $L_2$ is context-free. C $L_2,L_3$ and $L_2 \cap L_3$ all are context-free. D Neither $L_1$ nor its complement is context-free.
GATE CSE 2022   Theory of Computation
Question 1 Explanation:
 Question 2
Consider the following languages:

\begin{aligned} L_1&= \{a^n wa^n|w \in \{a,b \}^* \} \\ L_2&= \{wxw^R | w,x \in \{a,b \}^*, |w|,|x| \gt 0 \} \end{aligned}

Note that $w^R$ is the reversal of the string $w$. Which of the following is/are TRUE?
MSQ
 A $L_1$ and $L_2$ are regular. B $L_1$ and $L_2$ are context-free. C $L_1$ is regular and $L_2$ is context-free. D $L_1$ and $L_2$ are context-free but not regular.
GATE CSE 2022   Theory of Computation
Question 2 Explanation:
 Question 3
For a string $w$, we define $w^R$ to be the reverse of $w$. For example, if $w=01101$ then $w^R=10110$.
Which of the following languages is/are context-free?
[MSQ]
 A $\{ wxw^Rx^R \mid w,x \in \{0,1\} ^* \}$ B $\{ ww^Rxx^R \mid w,x \in \{0,1\} ^* \}$ C $\{ wxw^R \mid w,x \in \{0,1\} ^* \}$ D $\{ wxx^Rw^R \mid w,x \in \{0,1\} ^* \}$
GATE CSE 2021 SET-2   Theory of Computation
Question 3 Explanation:
 Question 4
Let $L_1$ be a regular language and $L_2$ be a context-free language. Which of the following languages is/are context-free?
[MSQ]
 A $L_1 \cap \overline{L_2}$ B $\overline{\overline{L_1} \cup \overline{L_2}}$ C $L_1 \cup (L_2 \cup \overline{L_2})$ D $(L_1 \cap L_2) \cup (\overline{L_1} \cap L_2)$
GATE CSE 2021 SET-2   Theory of Computation
Question 4 Explanation:
 Question 5
Suppose that $L_1$ is a regular language and $L_2$ is a context-free language. Which one of the following languages is NOT necessarily context-free?
 A $L_1\cap L_2$ B $L_1\cdot L_2$ C $L_1 - L_2$ D $L_1\cup L_2$
GATE CSE 2021 SET-1   Theory of Computation
Question 5 Explanation:
 Question 6
Consider the following languages.
$L_1=\{wxyx|w,x,y \in (0+1)^+\}$
$L_2=\{xy|x,y \in (a+b)^*,|x|=|y|,x\neq y\}$

Which one of the following is TRUE?
 A $L_1$ is regular and $L_2$ is context- free. B $L_1$ context- free but not regular and $L_2$ is context-free. C Neither $L_1$ nor $L_2$ is context- free. D $L_1$ context- free but $L_2$ is not context-free.
GATE CSE 2020   Theory of Computation
Question 6 Explanation:
 Question 7
Consider the language $L=\{a^n|n\geq 0\}\cup \{a^nb^n|n\geq 0\}$ and the following statements.

I. L is deterministic context-free.
II. L is context-free but not deterministic context-free.
III. L is not LL(k) for any k.

Which of the above statements is/are TRUE?
 A I only B II only C I and III only D III only
GATE CSE 2020   Theory of Computation
Question 7 Explanation:
 Question 8
Which one of the following languages over $\Sigma =\{a,b\}$ is NOT context-free?
 A $\{ww^R|w \in \{a,b\}^*\}$ B $\{wa^nb^nw^R|w \in \{a,b\}^*,n\geq 0\}$ C $\{wa^nw^Rb^n|w \in \{a,b\}^*,n\geq 0\}$ D $\{a^nb^i|i \in \{n,3n,5n\},n\geq 0\}$
GATE CSE 2019   Theory of Computation
Question 8 Explanation:
 Question 9
Consider the following languages:

I. $\{a^{m}b^{n}c^{p}d^{q}|m+p=n+q, \; where \; m,n,p,q \geq 0 \}$
II. $\{a^{m}b^{n}c^{p}d^{q}|m=n \; and \; p=q, \; where \; m,n,p,q\geq 0 \}$
III. $\{a^{m}b^{n}c^{p}d^{q}|m=n=p \; and \; p\neq q, \; where \; m,n,p,q\geq 0 \}$
IV. $\{a^{m}b^{n}c^{p}d^{q}|mn=p+q, \; where\; m,n,p,q\geq 0\}$

Which of the languages above are context-free?
 A I and IV only B I and II only C II and III only D II and IV only
GATE CSE 2018   Theory of Computation
Question 9 Explanation:
 Question 10
Consider the following languages

$L_{1}=\{a^{p}|p$ is a prime number}
$L_{2}=\{a^{n}b^{m}c^{2m}|n\geq 0,m\geq 0\}$
$L_{3}=\{a^{n}b^{n}c^{2n}|n\geq 0\}$
$L_{4}=\{a^{n}b^{n}|n\geq 1\}$

Which of the following are CORRECT ?

I.$L_{1}$ is context-free but not regular.
II. $L_{2}$ is not context-free.
III. $L_{3}$ is not context-free but recursive.
IV. $L_{4}$ is deterministic context-free.
 A I ,II and IV only B II and III only C I and IV only D III and IV only
GATE CSE 2017 SET-2   Theory of Computation
Question 10 Explanation:
There are 10 questions to complete.

### 10 thoughts on “Context Free Language”

1. Question 14 4th point L2 is complement PLZZ correct it. 🙏

2. In question no 21 check the power of B in L1. 🙏

3. 17th Question and option , both are wrong .

• Thank You shivam,

4. In Question 13, Both B and C options are the same.

• Thank You Rashmi,
We have updated the option.

5. question no. 13 option b and c both are same , please update