GATE CSE 2023 | Finite Automata and Regular Language Question 8 | Theory of Computation

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)

GATE CSE 2023 Theory of Computation - Finite Automata and Regular Language Question 8 English Option 1

GATE CSE 2023 Theory of Computation - Finite Automata and Regular Language Question 8 English Option 2

GATE CSE 2023

MCQ (More than One Correct Answer)

-0.33

Which of the following statements is/are CORRECT?

The intersection of two regular languages is regular.

The intersection of two context-free languages is context-free.

The intersection of two recursive languages is recursive.

The intersection of two recursively enumerable languages is recursively enumerable.

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 11 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 2021 Set 2

MCQ (Single Correct Answer)

-0.33

Let L ⊆ {0,1}* be an arbitrary regular language accepted by a minimal DFA with k states. Which one of the following languages must necessarily be accepted by a minimal DFA with k states?

{0,1}* - L

L.L

L - {01}

L ∪ {01}

PREVIOUS NEXT