Skip to main content

Gate Questions on Regular Expressions

Q1. Which two of the following four regular expressions are equivalent? (ε is the empty string).
(i) (00)*(ε + 0)
(ii) (00)*
(iii) 0*
(iv) 0(00)*

(a) (i) & (ii)      (b) (ii) & (iii)      (c) (i) & (iii)      (d) (iii) & (iv)    


Option (b) is correct.

i. (00)*( ε + 0) = (00)*ε + (00)*0 = (00)* + (00)*0 = 0*
Note that (00)* Generates strings of even length and (00)*0 generated the strings of odd length. Since + operator Union of both sets results in 0*.

Q2. The string 1101 does not belong the set represented by
(a) 110*(0+1)
(b) 1(0+1)*101
(c) (10)*(01)*(00+11)*
(d) (00+(11)*0)*

Both option (c) and (d) will not generate the string 1101

Q3. if the regular set A is represented by A = (01+1)* an the regular set B is represented by B = ((01)*1*)*, which of the following is true?
(a) A Ì B
(b) B Ì A
(c) A and B are incomparable
(d) A = B

Option d is true.

A = (01+1)* 
A = ( (01)* 1* )*       -- from rule (r1 + r2)* =( r1*r2*)*
A = B

If r1 and r2 are two regular expressions then,
      (r1 + r2)* = (r1* + r2*)*
                   = (r1* + r2)*
                   = (r1 + r2*)*
                   = (r1* . r2*)*

Q4. Let S and T be languages over ∑ = {a,b} represented by the regular expression (a + b*)* and (a + b)*, respectively. Which of the following is true?

(a) S Ì T
(b) T Ì S
(c) S = T
(d) S È T = f

Option c is true. From rule (r1 + r2)* =( r1 + r2*)*.
Note: Both S and T will generate the same language.


Popular posts from this blog

ORACLE 9i practice solutions

Created by BCL easyConverter SDK 3 (HTML Version)

Zoho Puzzle Questions With Answers

Measuring Time Logic Puzzle You are given with two ropes with variable width. However if we start burning both the ropes, they will burn at exactly same time i.e. an hour. The ropes are non-homogeneous in nature. You are asked to measure 45 minutes by using these two ropes.

How can you do it?

Please note that you can’t break the rope in half as it is being clearly stated that the ropes are non-homogeneous in nature.
Answer & Explanation Solution: 45 minutes

Explanation :
All you have to do is burn the first rope from both the ends and the second rope from one end only simultaneously. The first rope will burn in 30 minutes (half of an hour since we burned from both sides) while the other rope would have burnt half. At this moment, light the second rope from the other end as well. Where, the second rope would have taken half an hour more to burn completely, it will take just 15 minutes as we have lit it from the other end too.

Thus you have successfully calculated 30+15 = 45 minutes …

Hackerrank > SQL > Basic Select

01-Select All
Given a City table, whose fields are described as +-------------+----------+ | Field       | Type     | +-------------+----------+ | ID          | int(11)  | | Name        | char(35) | | CountryCode | char(3)  | | District    | char(20) | | Population  | int(11)  | +-------------+----------+
write a query that will fetch all columns for every row in the table.

My Solution
02-Select by ID
Given a City table, whose fields are described as