1
GATE CSE 2022
MCQ (More than One Correct Answer)
+1
-0.33

Which of the following is/are undecidable?

A
Given two Turing machines M1 and M2, decide if L(M1) = L(M2).
B
Given a Turing machine M, decide if L(M) is regular.
C
Given a Turing machine M, decide if M accepts all strings.
D
Given a Turing machine M, decide if M takes more than 1073 steps on every string.
2
GATE CSE 2022
MCQ (More than One Correct Answer)
+1
-0.33

Consider the following languages:

L1 = {an wan | w $$\in$$ {a, b}*}

L2 = {wxwR | w, x $$\in$$ {a, b}*, | w | , | x | > 0}

Note that wR is the reversal of the string w. Which of the following is/are TRUE?

A
L1 and L2 are regular.
B
L1 and L2 are context-free
C
L1 is regular and L2 is context-free.
D
L1 and L2 are context-free but not regular.
3
GATE CSE 2022
MCQ (More than One Correct Answer)
+1
-0.33

Consider the following languages:

$$\eqalign{ & {L_1} = \{ ww|w \in \{ a,b\} *\} \cr & {L_2} = \{ {a^n}{b^n}{c^m}|m,\,n \ge 0\} \cr & {L_3} = \{ {a^m}{b^n}{c^n}|m,\,n \ge 0\} \cr} $$

Which of the following statements is/are FALSE?

A
L1 is not context-free but L2 and L2 are deterministic context-free.
B
Neither L1 nor L2 is context-free.
C
L2, L3 and L2 $$\cap$$ L3 all are context-free.
D
Neither L1 nor its complement is context-free.
4
GATE CSE 2022
MCQ (Single Correct Answer)
+1
-0.33

The ___________ is too high for it to be considered __________.

A
fair / fare
B
faer / fair
C
fare / fare
D
fare / fair
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
CBSE
Class 12