GATE CS Regular Expressions and Finite Automata questions

Practise Regular Expressions and Finite Automata questions for GATE CS. Explore official PYQs and original topic-wise quizzes, check answers and view available solutions. Free, no sign-in.

14 on this page

SubjectTopicYearType

Consider the regular expression

(0 + 1) (0+1) \dots N

times. The minimum state finite automaton that recognizes the language represented by this regular expression contains

Let

L

be the set of all binary strings whose last two symbols are the same. The number of states in the minimal state deterministic finite state automaton accepting

L

The string

1101

does not belong to the set represented by

Regarding the power of recognition of languages, which of the following statements is false?

Which of the following set can be recognized by a Deterministic Finite state Automaton?

If the regular set

A

is represented by

A = (01 + 1)^*

and the regular set

B

is represented by

B = \left(\left(01\right)^*1^*\right)^*

, which of the following is true?

Which one of the following regular expressions over

\{0,1\}

denotes the set of all strings not containing

\text{100}

as substring?

Which two of the following four regular expressions are equivalent? (

\varepsilon

is the empty string).

(00)^ * (\varepsilon +0)

(00)^*

0^*

0(00)^*

In some programming language, an identifier is permitted to be a letter followed by any number of letters or digits. If

L

and

D

denote the sets of letters and digits respectively, which of the following expressions defines an identifier?

Which of the following conversions is not possible (algorithmically)?

In which of the cases stated below is the following statement true? "For every non-deterministic machine

M_{1}

there exists an equivalent deterministic machine

M_{2}

recognizing the same language".

Which of the following regular expression identities is/are TRUE?

Let

r=1(1+0)^*, s=11^*0 \text{ and } t=1^*0

be three regular expressions. Which one of the following is true?

State whether the following statements are TRUE or FALSE: A minimal DFA that is equivalent to an NDFA with

n

nodes has always

2^{n}

states.