# Context Free Language

 Question 1
Which of the following statements is/are CORRECT?
 A The intersection of two regular languages is regular. B The intersection of two context-free languages is context-free. C The intersection of two recursive languages is recursive. D The intersection of two recursively enumerable languages is recursively enumerable.
GATE CSE 2023   Theory of Computation
Question 1 Explanation:
 Question 2
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 2 Explanation:

 Question 3
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 3 Explanation:
 Question 4
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 4 Explanation:
 Question 5
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 5 Explanation:

There are 5 questions to complete.

### 12 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

• Thank You dp kushwaha,
We have updated the option.

6. question no. 26 wrong please update with L intersection M

• Thank You dp,
We have updated the question.

7. • 