Context Free Language

Question 1
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 2
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 3
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 4
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 5
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 6
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 7
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 8
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 9
Let L_{1},L_{2} be any two context free languages and R be any regular language. Then which of the following is/are CORRECT ?
I. L_{1}\cup L_{2} is context - free
II. \bar{L_{1}} is context - free
III. L_{1} - R is context - free
IV. L_{1}\cap L_{2} is context - free
A
I, II and IV only
B
I and III only
C
II and IV only
D
I only
GATE CSE 2017 SET-2   Theory of Computation
Question 10
Consider the following languages over the alphabet \Sigma = \{a, b,c\}.
Let L_{1}=\{a^{n}b^{n}c^{m}|m,n\geq 0\} and L_{2}=\{a^{m}b^{n}c^{n}|m,n\geq 0\}

Which of the following are context-free languages ?
I. L_{1}\cup L_{2}
II. L_{1}\cap L_{2}
A
I only
B
II only
C
I and II
D
Neither I nor II
GATE CSE 2017 SET-1   Theory of Computation
There are 10 questions to complete.

10 thoughts on “Context Free Language”

Leave a Comment

Like this FREE website? Please share it among all your friends and join the campaign of FREE Education to ALL.