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)

C Questions

C Questions
C Questions

Note : All the programs are tested under Turbo C/C++ compilers.
It is assumed that,
Programs run under DOS environment, The underlying machine is an x86 system, Program is compiled using Turbo C/C++ compiler.
The program output may depend on the information based on this assumptions (for example sizeof(int) == 2 may be assumed).
Predict the output or error(s) for the following:

void main()
int const * p=5; printf("%d",++(*p));
Compiler error: Cannot modify a constant value.
p is a pointer to a "constant integer". But we tried to change the value of the "constant integer".
char s[ ]="man"; int i;
for(i=0;s[ i ];i++)
printf("\n%c%c%c%c",s[ i ],*(s+i),*(i+s),i[s]);
Answer: mmmm
aaaa nnnn

Zoho Interview | Set 1 (Advanced Programming Round)

Third Round: (Advanced Programming Round) Here they asked us to create a “Railway reservation system” and gave us 4 modules. The modules were:
    1. Booking
    2. Availability checking
    3. Cancellation
    4. Prepare chart
We were asked to create the modules for representing each data first and to continue with the implementation phase.

 My Solution :

#include<stdio.h>#include<conio.h>#include<stdlib.h>#include<string.h>#include<iostream.h>#include<time.h>#include<iomanip.h>#include<fstream.h>char f[10]="f";char s[10]="s";int addr,ad,flag,f1,d,m,i,amt;float tamt; class login {public:char id[100];char pass[100];char*password;void getid(){ cout<<"Enter your id:";gets(id); password=getpass("Enter the password:");strcpy(pass,password);}void displayid(){ cout<<"Id:";puts(id); cout<<"Password:";puts(pass);}}; class detail {public:in…