GATE CSE 2024 Set 1 | Finite Automata and Regular Language Question 10 | Theory of Computation

Theory of Computation

Finite Automata and Regular Language

Marks 1 Marks 2 Marks 5

Push Down Automata and Context Free Language

Marks 1 Marks 2

Undecidability

Marks 1 Marks 2

Recursively Enumerable Language and Turing Machine

Marks 1 Marks 2

Previous Next

GATE CSE 2024 Set 1

MCQ (More than One Correct Answer)

-0

Let $L_1, L_2$ be two regular languages and $L_3$ a language which is not regular. Which of the following statements is/are always TRUE?

$L_1 = L_2$ if and only if $L_1 \cap \overline{L_2} = \emptyset$

$L_1 \cup L_3$ is not regular

$\overline{L_3}$ is not regular

$L_1 \cup \overline{L_2}$ is regular

GATE CSE 2023

MCQ (Single Correct Answer)

-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$$?

$$1(0^*11)^*$$

$$0(0+1)^*$$

$$1(0+11)^*$$

$$1(110^*)^*$$

GATE CSE 2023

MCQ (Single Correct Answer)

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