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
\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
L_1 is not context-free but L_2 and L_3 are deterministic context-free. | |
Neither L_1 nor L_2 is context-free. | |
L_2,L_3 and L_2 \cap L_3 all are context-free. | |
Neither L_1 nor its complement is context-free. |
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
\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
L_1 and L_2 are regular. | |
L_1 and L_2 are context-free. | |
L_1 is regular and L_2 is context-free. | |
L_1 and L_2 are context-free but not regular. |
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]
Which of the following languages is/are context-free?
[MSQ]
\{ wxw^Rx^R \mid w,x \in \{0,1\} ^* \} | |
\{ ww^Rxx^R \mid w,x \in \{0,1\} ^* \} | |
\{ wxw^R \mid w,x \in \{0,1\} ^* \} | |
\{ wxx^Rw^R \mid w,x \in \{0,1\} ^* \} |
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]
[MSQ]
L_1 \cap \overline{L_2} | |
\overline{\overline{L_1} \cup \overline{L_2}} | |
L_1 \cup (L_2 \cup \overline{L_2}) | |
(L_1 \cap L_2) \cup (\overline{L_1} \cap L_2) |
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?
L_1\cap L_2 | |
L_1\cdot L_2 | |
L_1 - L_2 | |
L_1\cup L_2 |
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?
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?
L_1 is regular and L_2 is context- free. | |
L_1 context- free but not regular and L_2 is context-free. | |
Neither L_1 nor L_2 is context- free. | |
L_1 context- free but L_2 is not context-free. |
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?
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?
I only | |
II only | |
I and III only | |
III only |
Question 7 Explanation:
Question 8 |
Which one of the following languages over \Sigma =\{a,b\} is NOT context-free?
\{ww^R|w \in \{a,b\}^*\} | |
\{wa^nb^nw^R|w \in \{a,b\}^*,n\geq 0\} | |
\{wa^nw^Rb^n|w \in \{a,b\}^*,n\geq 0\} | |
\{a^nb^i|i \in \{n,3n,5n\},n\geq 0\} |
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?
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?
I and IV only | |
I and II only | |
II and III only | |
II and IV only |
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.
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.
I ,II and IV only | |
II and III only | |
I and IV only | |
III and IV only |
Question 10 Explanation:
There are 10 questions to complete.
Question 14 4th point L2 is complement PLZZ correct it. 🙏
In question no 21 check the power of B in L1. 🙏
17th Question and option , both are wrong .
please correct it .
Thank You shivam,
We have updated the answer.
In Question 13, Both B and C options are the same.
Thank You Rashmi,
We have updated the option.
question no. 13 option b and c both are same , please update
Thank You dp kushwaha,
We have updated the option.
question no. 26 wrong please update with L intersection M
Thank You dp,
We have updated the question.