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

Which of the following statements is/are TRUE?

A
Every subset of a recursively enumerable language is recursive.
B
If a language L and its complement $$\overline L$$ are both recursively enumerable, then L must be recursive.
C
Complement of a context-free language must be recursive.
D
If L1 and L2 are regular, then L1 $$\cap$$ L2 must be deterministic context-free.
2
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.
3
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.
4
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.
GATE CSE Papers
2023
2022
2020
2019
2018
2013
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
2000
1999
1998
1997
1996
1995
1994
1993
1992
1991
1990
1989
1988
1987
EXAM MAP
Medical
NEET