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 17 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 15 English Option 1
B
GATE CSE 2023 Theory of Computation - Finite Automata and Regular Language Question 15 English Option 2
C
GATE CSE 2023 Theory of Computation - Finite Automata and Regular Language Question 15 English Option 3
D
GATE CSE 2023 Theory of Computation - Finite Automata and Regular Language Question 15 English Option 4
3
GATE CSE 2023
MCQ (More than One Correct Answer)
+1
-0

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 18 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