1
GATE CSE 2023
MCQ (Single Correct Answer)
+1
-0.33

Consider the Deterministic Finite-state Automation (DFA) $$A$$ shown below. The DFA runs on the alphabet {0, 1}, and has the set of states {$$s,p,q,r$$}, with $$s$$ being the start state and $$p$$ being the only final state.

GATE CSE 2023 Theory of Computation - Finite Automata and Regular Language Question 10 English

Which one of the following regular expressions correctly describes the language accepted by $$A$$?

A
$$1(0^*11)^*$$
B
$$0(0+1)^*$$
C
$$1(0+11)^*$$
D
$$1(110^*)^*$$
2
GATE CSE 2023
MCQ (Single Correct Answer)
+1
-0.33

Consider the following definition of a lexical token id for an identifier in a programming language, using extended regular expressions:

$$\mathrm{letter\to[A-Za-z]}$$

$$\mathrm{letter\to[0-9]}$$

$$\mathrm{id\to letter(letter\,|\,digit)^*}$$

Which one of the following Non-deterministic Finite-state Automata with $$\varepsilon $$-transmissions accepts the set of valid identifiers? (A double-circle denotes a final state)

A
GATE CSE 2023 Theory of Computation - Finite Automata and Regular Language Question 8 English Option 1
B
GATE CSE 2023 Theory of Computation - Finite Automata and Regular Language Question 8 English Option 2
C
GATE CSE 2023 Theory of Computation - Finite Automata and Regular Language Question 8 English Option 3
D
GATE CSE 2023 Theory of Computation - Finite Automata and Regular Language Question 8 English Option 4
3
GATE CSE 2023
MCQ (More than One Correct Answer)
+1
-0.33

Which of the following statements is/are CORRECT?

A
The intersection of two regular languages is regular.
B
The intersection of two context-free languages is context-free.
C
The intersection of two recursive languages is recursive.
D
The intersection of two recursively enumerable languages is recursively enumerable.
4
GATE CSE 2022
MCQ (Single Correct Answer)
+1
-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 11 English

A
ab*bab* + ba*aba*
B
(ab*b)* ab* + (ba*a)*ba*
C
(ab*b + ba*a)* (a* + b*)
D
(ba*a + ab*b)* (ab* + ba*)
GATE CSE Subjects
Software Engineering
Web Technologies
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