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

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)
+2
-0

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)
+2
-0

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
NEETAIIMS
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
Defence
NDA
Staff Selection Commission
SSC CGL Tier I
CBSE
Class 12