GATE CSE 2022 | GATE CSE Year Wise Previous Years Questions

GATE CSE 2022

MCQ (Single Correct Answer)

-0.33

Which one of the following regular expressions correctly represents the language of the finite automation given below?

GATE CSE 2022 Theory of Computation - Finite Automata and Regular Language Question 2 English

ab*bab* + ba*aba*

(ab*b)* ab* + (ba*a)*ba*

(ab*b + ba*a)* (a* + b*)

(ba*a + ab*b)* (ab* + ba*)

GATE CSE 2022

MCQ (More than One Correct Answer)

-0.33

Which of the following statements is/are TRUE?

Every subset of a recursively enumerable language is recursive.

If a language L and its complement $$\overline L $$ are both recursively enumerable, then L must be recursive.

Complement of a context-free language must be recursive.

If L₁ and L₂ are regular, then L₁ $$\cap$$ L₂ must be deterministic context-free.

GATE CSE 2022

MCQ (More than One Correct Answer)

-0.33

Which of the following is/are undecidable?

Given two Turing machines M₁ and M₂, decide if L(M₁) = L(M₂).

Given a Turing machine M, decide if L(M) is regular.

Given a Turing machine M, decide if M accepts all strings.

Given a Turing machine M, decide if M takes more than 1073 steps on every string.

GATE CSE 2022

MCQ (More than One Correct Answer)

-0.33

Consider the following languages:

L₁ = {aⁿ waⁿ | w $$\in$$ {a, b}*}

L₂ = {wxw^R | w, x $$\in$$ {a, b}*, | w | , | x | > 0}

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

L₁ and L₂ are regular.

L₁ and L₂ are context-free

L₁ is regular and L₂ is context-free.

L₁ and L₂ are context-free but not regular.

PREVIOUS NEXT

GATE CSE Papers

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

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