Regular Expression


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

letter \rightarrow [A-Za-z]
digit \rightarrow [0-9]
id \rightarrow letter (letter\;| \;digit)^*


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

A
A
B
B
C
C
D
D
GATE CSE 2023   Theory of Computation
Question 2
Consider the Deterministic Finite-state Automaton (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.

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^*)^*
GATE CSE 2023   Theory of Computation


Question 3
Which of the following regular expressions represent(s) the set of all binary numbers that are divisible by three? Assume that the string \epsilon is divisible by three.
[MSQ]
A
(0+1(01^*0)^*1)^*
B
(0+11+10(1+00)^*01)^*
C
(0^*(1(01^*0)^*1)^*)^*
D
(0+11+11(1+00)^*00)^*
GATE CSE 2021 SET-2   Theory of Computation
Question 4
Which one of the following regular expressions represents the set of all binary strings with an odd number of 1's?
A
((0+1)^* 1(0+1)^*1)^*10^*
B
(0^*10^*10^*)^*0^*1
C
10^*(0^*10^*10^*)^*
D
(0^*10^*10^*)^*10^*
GATE CSE 2020   Theory of Computation
Question 5
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?
A
(L+D)^{+}
B
\text { (L.D)* }
C
L(L+D)^{*}
D
L(L . D)^{*}
ISRO CSE 2017   Theory of Computation


There are 5 questions to complete.

10 thoughts on “Regular Expression”

Leave a Comment