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


There are 5 questions to complete.

12 thoughts on “Context Free Language”

  7. pls not allow ads which ask money in the name of their child illness. In between solving question, they cry so hard that makes uncomfortable.
    other ads are OK.

    Reply

Leave a Comment