GATE 2024 Theory of computation Foundation Quiz 87

Consider the following sentences:

1) Regular expressions that do not contain the star operator (Kleene Star Operator or Kleene Plus Operator) can represent only finite languages.

2) For every pair of regular expressions R and S, the language denotes by R(SR)* and (RS)*R are the same.

Which of the above is/are Correct?

Consider the regular expression (a+b) (a+b) .... (a+b) (n-times). The minimum number of states in finite automaton that recognizes the language represented by this regular expression contains:

Match each NFA with an equivalent regular expression from the list below

(i) ∈ + 1(10*1 + 10)*0

(ii) ∈ + 0(01*1 + 00)*01*

(iii) ∈ + 0(10*1 + 10)*10*

(iv) ∈ + 0(10*1 + 00)*0

(v) ∈ + 0(10*1 + 10)*0

(vi) ∈ + 0(01*1 + 10)*0

(vii) ∈ + 0(10*1 + 10)*1

Consider the following regular expressions:

R1: a(a+b)^*

R2: (a+b)*b

Select the option which is Incorrect.

Consider the following regular expression (RE)

RE = 

How many minimal strings exist for the above RE?