# 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 1 Explanation:
 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 2 Explanation:

 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 3 Explanation:
 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 4 Explanation:
 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
Question 5 Explanation:

There are 5 questions to complete.

### 10 thoughts on “Regular Expression”

1. Options wrong

• Please specify the question number and option which you fell as wrong.

• 7th C option is wrong

• Thank You shivam,
We have updated the option C.

2. Useful.Thank you

3. Q11 options A and B don’t have a final state.

• Thank You,
We have updated the figure as per your suggestion.

4. In question 14 c and d options are the same

• 5. 