Theory of Computation GATE Question Answers with Explanation.
Q1 – Which one of the following regular expressions correctly represents the language of the finite automaton given below?
 (GATE 2022)
Â
1. ab*bab* + ba*aba*
2. (ab*b)*ab* + (ba*a)*ba*
3. (ab*b + ba*a)* (a* + b*)
4. (ba*a + ab*b)*(ab* + ba*)
Ans – (4)
Explanation –
Q2 – Which of the following statements is/are TRUE? (GATE 2022)
Â
1. Every subset of a recursively enumerable language is recursive.
2. If a language L and its complement L’ are both recursively enumerable, then L must be recursive.
3. Complement of a context-free language must be recursive.
4. If L1 and L2 are regular, then L1 ∩ L2 must be deterministic context-free.
Ans – (2, 3, 4)Â
Explanation –
Q3 – Which of the following is/are undecidable? (GATE 2022)
Â
1. Given two Turing machines M1 and M2, decide if L(M1) = L(M2).
2. Given a Turing machine M, decide if L(M) is regular.
3. Given a Turing machine M, decide if M accepts all strings.
4. Given a Turing machine M, decide if M takes more than 1073 steps on every string.
Ans – (1, 2, 3)
Explanation –
Q4 – Consider the following languages:
L1 = {anwan | w ϵ {a,b}*}
L2 = {wxwR | w, x ϵ{a,b}* , | w|,| x |> 0}
Note that wR is the reversal of the string w. Which of the following is/are TRUE? (GATE 2022)
Â
1. L1 and L2 are regular.
2. L1 and L2 are context-free.
3. L1 is regular and L2 is context-free.
4. L1 and L2 are context-free but not regular.
Ans – (1, 2, 3)
Explanation –
Q5 – Consider the following languages:
L1 = {ww| w ϵ {a, b}*}
L2 = {an bn cm |m, n ≥ 0}
L3 = {am bn cn |m, n ≥ 0}
Which of the following statements is/are FALSE? (GATE 2022)
Â
1. L1 is not context-free but L2 and L3 are deterministic context-free.
2. Neither L1 nor L2 is context-free.
3. L2, L3 and L2 ∩ L3 all are context-free.
4. Neither L1 nor its complement is context-free.
Ans – (2, 3, 4)
Explanation –