NEW
Font size
WorksheetsRegular expression Session 2020-21
Total questions: 20
Worksheet time: 10mins
1. Regular expressions are used to represent which language
Recursive language
Context free language
Regular language
All of these
Which of the following operation can be applied on regular expressions?
Union
Concatenation
Closure
All of these
The set of all strings over ∑ = {0,1} in which all strings that beings and ends with 0 is
0(0+1)0
00
00(0+1)0
All of these
The set of all strings over ∑ = {a,b} in which all strings having bbbb as substring is
(a+b)* bbbb (a+b)*
(a+b)* bb (a+b)*bb
bbbb (a+b)*
bb (a+b)*
The set of all strings over ∑ ={a,b} in which a single a is followed by any number of b’s a single b followed by any number of a’s is:
ab* + ba*
ab*ba*
a*b + b*a
None
The set of all strings over ∑ = {a,b} in which all strings of a’s and b’s ending in bb is
ab
a*bbb
(a+b)* bb
All of these
Which of the following identity is wrong?
R + R = R
(R*)* = R*
ɛR = Rɛ = R
ØR = RØ = RR*
Which of the following statement is true?
Every language that is defined by regular expression can also be defined by finite automata
Every language defined by finite automata can also be defined by regular expression
We can convert regular expressions into finite automata
All of these
If P, Q, R are three regular expressions and if P does not contain a then the equation R = R + RP has a unique solution given by
R = QP*
R = P*Q
R = RP
None
If P, Q, R are three regular expressions and if P does not contain ____________ then the equation ___________ has a unique solution given by R=QP*
One, R=Q+PQ
Null, R=Q+RP
Null, R=Q+QP*
Null, R=QP*
How many strings of length less than 4 contains the language described by the regular expression (x+y)*y(a+ab)*?
7
10
12
11
Which of the following is true?
(01)*0 = 0(10)*
(0+1)*01(0+1)*+1*0* = (0+1)*
(0+1)*0(0+1)*1(0+1) = (0+1)*01(0+1)*
All of above
Which of the following is true?
Every subset of a regular set is regular
Every finite subset of non-regular set is regular
The union of two non regular set is not regular
Infinite union of finite set is regular
Consider the following two statements:
S1: { 0^2n |n >= l} is a regular language
S2: { 0^m 0^n 0^(m+n) l m >= 1 and n >= 2} is a regular language
Which of the following statements is correct?
Only S1 is correct
Only S2 is correct
Both S1 and S2 are correct
None of S1 and S2 is correct
Which of the following statements in true? (GATE CS 2001)
If a language is context free it can always be accepted by a deterministic push-down automaton
The union of two context free languages is context free
The intersection of two context free languages is context free
The complement of a context free language is context free
Let M= (Q, Σ, δ, S, F) and M’= (Q, Σ, δ, S, Q – F) where M accepts L and M’ accepts L1 and M is NFA, which among the following is the relation between L and L’ ?
L and L’ are complement to each other
L and L’ are similar to each other
L and L’ relation cannot be predicted
None of the above
Grammar has _______tuple in which S represents_________.
3, production rules
5, starting variable
4, starting variable
4, production rules
An NFA’s transition function returns
State
boolean value
A set of states
None of these
in pumping lemma, string w can be decomposed into:
w=xyz, where y can not be null
w=xyz, where y may be null
x=yaz
w=yzx
A push down automaton employs ________ data structure.
Queue
Linked List
Hash Table
Stack
