Computer Science Engineering (CSE)  >  RRB JE for Computer Science Engineering  >  Test: Regular Expressions & Languages- 2 Download as PDF

Test: Regular Expressions & Languages- 2


Test Description

30 Questions MCQ Test RRB JE for Computer Science Engineering | Test: Regular Expressions & Languages- 2

Test: Regular Expressions & Languages- 2 for Computer Science Engineering (CSE) 2022 is part of RRB JE for Computer Science Engineering preparation. The Test: Regular Expressions & Languages- 2 questions and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus.The Test: Regular Expressions & Languages- 2 MCQs are made for Computer Science Engineering (CSE) 2022 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests for Test: Regular Expressions & Languages- 2 below.
Solutions of Test: Regular Expressions & Languages- 2 questions in English are available as part of our RRB JE for Computer Science Engineering for Computer Science Engineering (CSE) & Test: Regular Expressions & Languages- 2 solutions in Hindi for RRB JE for Computer Science Engineering course. Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Attempt Test: Regular Expressions & Languages- 2 | 30 questions in 90 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study RRB JE for Computer Science Engineering for Computer Science Engineering (CSE) Exam | Download free PDF with solutions
1 Crore+ students have signed up on EduRev. Have you?
Test: Regular Expressions & Languages- 2 - Question 1

Consider the regular grammar below

The Myhill-Nerode equivalence classes for the language generated by the grammar are

Detailed Solution for Test: Regular Expressions & Languages- 2 - Question 1

The given grammar generates all string over the alphabet {a,b}  which have an even number of 's.
The given right-linear grammar can be converted to the following DFA.

Test: Regular Expressions & Languages- 2 - Question 2

Consider the alphabet ∑ = {0,1} , the null/empty string λ  and the set of strings X0,X1 and X2  generated by the corresponding non-terminals of a regular grammar. X0,X1 and X2  are related as follows.

Which one of the following choices precisely represents the strings in X0?

Detailed Solution for Test: Regular Expressions & Languages- 2 - Question 2

Here we have little different version of Arden's Theorem

if we have R= PR + Q   then it has a solution  R = P*Q

Proof : R= PR+ Q
= P(PR+Q)+Q    (by putting R= PR+Q)

= PPR+PQ+Q

=PP(PR+Q)+PQ+Q   (by putting R= PR+Q)

= PPPR+PPQ+PQ+Q

and so on , we get R

= {..........+PPPPQ+PPPQ+PPQ+PQ+Q}          = {..........+PPPP+PPP+PP+P+ ^}Q  = P*Q

or Another way R=PR+Q

= P(P*Q) + Q      (by putting R = P*Q)

=(PP* + ^)Q = P*Q

So Equation is Proved .

Now for the Above Question

X1= 0X1 + 1 X2   (Equation 2)

= 0X1 +1(0X1 + ^)     ( Put the value of X2 from Equation 3 )

=0X1 +10 X1+ 1 =  (0+10)X1 +1

X1= (0+10)*1   (Apply if R = PR + Q then R = P*Q)

X0 = 1 X1     ( Equation 1)

X0 = 1(0+10)*1   ( Put the value of X1 we calculated).
So  1(0+10)*1   option C is correct.

Test: Regular Expressions & Languages- 2 - Question 3

  Which of the following is true?

Detailed Solution for Test: Regular Expressions & Languages- 2 - Question 3

Ans C) Every finite subset should always be regular

A set may be regular

It's all subset is not regular all the time

Say (0+1)* is regular but 0n1n is not regular

Test: Regular Expressions & Languages- 2 - Question 4

Let L1 and L2 be languages over an alphabet £ such that L1 ⊂ L2. Which of the following is true

Detailed Solution for Test: Regular Expressions & Languages- 2 - Question 4

Contradiction for A. Let L2 = {a,b}* ... which is regular.

And L1 = anbn which is CFL but not regular.

And here L1 is subset of L2.

Contradiction for B. Let L1 = ab ,

which is regular. And L2 = anbn which is CFL but not regular.

And here L1 is subset of L2.

C- > False , ( reason A and B).

Test: Regular Expressions & Languages- 2 - Question 5

Language L1  is defined by the grammar: 

Language L2  is defined by the grammar:  

Consider the following statements:

Which one of the following is TRUE?

Detailed Solution for Test: Regular Expressions & Languages- 2 - Question 5

is Regular having regular expression  (ab)*.

*Multiple options can be correct
Test: Regular Expressions & Languages- 2 - Question 6

Choose the correct alternatives (More than one may be correct).

Let R1 and R2 be regular sets defined over the alphabet ∑  Then:

Detailed Solution for Test: Regular Expressions & Languages- 2 - Question 6

Regular Languages are closed under 1. Intersection 2. Union 3. Complement 4. Kleen-Closure ∑∗−R1 is the complement of R1

B,C are true

*Multiple options can be correct
Test: Regular Expressions & Languages- 2 - Question 7

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: Which of the following is the strongest correct statement about a finite language over some finite alphabet  ?

Detailed Solution for Test: Regular Expressions & Languages- 2 - Question 7

(b), (c) and (d) are true. But the strongest answer would be (d) a regular language. It is trivial to say that a finite set of strings (finite language) can be accepted using a finite set of states. And regular language ⊂ context-free ⊂ contextsensitive ⊂ Turing recognizable, would imply that regular language is the strongest answer. 

Test: Regular Expressions & Languages- 2 - Question 8

  then the languages    are respectively

Detailed Solution for Test: Regular Expressions & Languages- 2 - Question 8

 is a subset of  L  and hence regular. R is deterministic context-free but not regular as we require a stack to keep the count of 0's to match that of 1's.

Test: Regular Expressions & Languages- 2 - Question 9

Which of the following statements is false?

Detailed Solution for Test: Regular Expressions & Languages- 2 - Question 9

Any language is a subset of ∑* which is a regular set. So, if we take any non-regular language, it is a subset of a regular language.

(a) and (c) are regular as any finite language is regular.

(d) is regular as regular set is closed under intersection.

Test: Regular Expressions & Languages- 2 - Question 10

  Which of the following is true?

Detailed Solution for Test: Regular Expressions & Languages- 2 - Question 10

Only D. because n and m are independent and thus no memory element required. a and b are same and are DCFL's.

c is L = { an bm | n > m }. which is not regular.
Correction:I think c should be that x has more a's than b's.

Test: Regular Expressions & Languages- 2 - Question 11

What can be said about a regular language L over { a } whose minimal finite state automaton has two states?

Detailed Solution for Test: Regular Expressions & Languages- 2 - Question 11

Because if we draw the minimal dfa for each of them, we will get two states each.
Whereas, {an| n>=0} requires only one state.

Test: Regular Expressions & Languages- 2 - Question 12

Consider the following two statements:

Which of the following statement is correct?

Detailed Solution for Test: Regular Expressions & Languages- 2 - Question 12

Only s1 is correct a dfa with 2 states where one of the states is both the initial and final state..

Test: Regular Expressions & Languages- 2 - Question 13

Consider the following languages:

Which of the languages are regular?

Detailed Solution for Test: Regular Expressions & Languages- 2 - Question 13

 Linear Power and regular expression can be stated as

  non linear power So CSL

 

Test: Regular Expressions & Languages- 2 - Question 14

If s is a string over (0+1)*  then let n0(s) denote the number of 0’s in s and n1(s) the number of 1’s in s. Which one of the following languages is not regular ?

Detailed Solution for Test: Regular Expressions & Languages- 2 - Question 14

A. There are only finite 3 digit primes. And any finite set is regular

B. Here we need just 6 states to recognise L. 

If the difference goes above 2 or below -2, we go to a dead state. All other states are accepting. This transition to dead state is possible because of the words "for every prefix s' of s" in L and that is what makes this language regular. 

C. L is not regular

All these form distinct equivalent classes under Myhill-Nerode theorem meaning from the strings in each of these sets, we can append a string which will take the new string to L, while the same string appended to string in any other set won't reach L. 

For example, for 000000, we append 11, for 0000000, we append 111 etc. So, in short we need to maintain the count of 1's and 0's and the count here is not finite.

D. This is regular. We need a finite automata with 5 * 7 = 35 states for maintaining the counts of 0's mod 7 and 1's mod 5 and there cannot be more than 35 possibilities for this. With each input symbol, the transition must be going to one among these. 

Test: Regular Expressions & Languages- 2 - Question 15

Which of the following statements about regular languages is NOT true ?

Detailed Solution for Test: Regular Expressions & Languages- 2 - Question 15

A) Every language has a regular superset: True. ∑*  is such a superset.

B) Every language has a regular subset: True. Ø is such a subset.

C) Every subset of a regular language is regular: False. 

D) Every subset of a finite language is regular: True. Every subset of a finite set must be finite by definition. Every finite set is regular. Hence, every subset of a finite language is regular.

Test: Regular Expressions & Languages- 2 - Question 16

Let L be a regular language. Consider the constructions on L below:

Which of the constructions could lead to a non-regular language?

Detailed Solution for Test: Regular Expressions & Languages- 2 - Question 16

correct answer is B. only 1 .

Test: Regular Expressions & Languages- 2 - Question 17

Which of the following languages is regular?

Detailed Solution for Test: Regular Expressions & Languages- 2 - Question 17

A. CFL
B. CFL
C. Regular, language is string starting and ending with the same symbol and having length at least 3. e.g. 0x0 or 1x1
D. CFL

Test: Regular Expressions & Languages- 2 - Question 18

Which of the following is TRUE?

Detailed Solution for Test: Regular Expressions & Languages- 2 - Question 18

(B) Every finite subset of a non-regular set is regular.
Any finite set is always regular. 

∑* being regular any non regular language is a subset of this, and hence (A) is false.

If we take a CFL which is not regular, and takes union with its complement (complement of a CFL which is not regular won't be regular as regular is closed under complement), we get ∑* which is regular. So, (C) is false. 

Regular set is not closed under infinite union. Example: Let Li = {0i1i }, i ∊ N

Now, if we take infinite union over all i, we get

L = {0i1i | i ∊ N}, which is not regular. So, D is false. 

Test: Regular Expressions & Languages- 2 - Question 19

Which of the following languages is (are) non-regular?

  reads the same forward and backward}

    contains an even number of 0's and an even number of 1's}

Detailed Solution for Test: Regular Expressions & Languages- 2 - Question 19

L1 is regular.. since 10000 is finite.. so finite states are required..
L3 is also regular.. we can make DFA for L3.. states will represent mod 2 for 0 and mod 2 for 1, which is finite

L2 is non. regular.. it is CFG S->aSa | ... | zSz | epsilon | [a-z]

Test: Regular Expressions & Languages- 2 - Question 20

Which of the following are regular sets?

Detailed Solution for Test: Regular Expressions & Languages- 2 - Question 20

Since in option 2 and 3, n is dependent on m, therefore a comparison has to be done to evaluate those and hence are not regular.

I and IV are clearly regular sets.

Test: Regular Expressions & Languages- 2 - Question 21

Let P be a regular language and Q be a context-free language such that    (For example, let P be the language represented by the regular expression    Then which of the following is ALWAYS regular? 

Detailed Solution for Test: Regular Expressions & Languages- 2 - Question 21

c)complement of regular Language is regular

Test: Regular Expressions & Languages- 2 - Question 22

Given the language    which of the following strings are in L*? 

Detailed Solution for Test: Regular Expressions & Languages- 2 - Question 22

  L = {ab,aa,baa}   

1. abaabaaabaa    =   ab    aa   baa  ab  aa       belong to L* (combinations of strings in L)

2. aaaabaaaa        =   aa    aa  baa  aa              belong to L*

3. baaaaabaaaab  = baa  aa  ab  aa aa  b does not belong to L*

4. baaaaabaa        = baa  aa  ab  aa                 belong to L*

 

Test: Regular Expressions & Languages- 2 - Question 23

Consider the languages     Which one of the following represents  

Detailed Solution for Test: Regular Expressions & Languages- 2 - Question 23

Concatenation of empty language with any language will give the empty language and 

Therefore,

Hence option (a) is True.

PS: φ   = ∈ , where ∈ is the regular expression and the language it generates is {∈}.

Test: Regular Expressions & Languages- 2 - Question 24

Which one of the following is TRUE?

Detailed Solution for Test: Regular Expressions & Languages- 2 - Question 24

(A) is CFL and (B) and (D) are CSL. (C) is regular and regular expression for (C) would be

Test: Regular Expressions & Languages- 2 - Question 25

Which one of the following is CORRECT?

Detailed Solution for Test: Regular Expressions & Languages- 2 - Question 25

(Also, since both L1 and L2 are Regular, their concatenation has to be Regular since Regular languages are closed under concatenation)

However, L1.L2 ≠anbn . This is because in a*b* , the number of 's and 's can be different whereas in  they have to be the same.

Test: Regular Expressions & Languages- 2 - Question 26

Which of the following is/are regular languages?

  ,  is the reverse of string ω

Detailed Solution for Test: Regular Expressions & Languages- 2 - Question 26

L3 is simple to guess, it is regular. Below is DFA for L1.
Q67
L1 is interesting. The important thing to note about L1 is length of x is greater than 0, i.e., |x| > 0. So any string than starts and ends with same character is acceptable by language and remaining string becomes w. Below is DFA for L1.
Q68

Test: Regular Expressions & Languages- 2 - Question 27

Consider the following three statements:

(i) Intersection of infinitely many regular languages must be regular.

(ii) Every subset of a regular language is regular.

(iii) If L is regular and M is not regular then L.M is necessarily not regular.

Which of the following gives the correct true/false evaluation of the above?

Detailed Solution for Test: Regular Expressions & Languages- 2 - Question 27

i) False

Regular Languages are not closed under Infinite Union and Intersection 

As Infinite Union is not closed , So Infinite Intersection is also not closed 

ii) False. 

iii) False 

Test: Regular Expressions & Languages- 2 - Question 28

Let B  consist of all binary strings beginning with a 1 whose value when converted to decimal is divisible by 7 .

Detailed Solution for Test: Regular Expressions & Languages- 2 - Question 28

if it start with 1 it goes to final state

if start with 0 it will go to the reject state

Test: Regular Expressions & Languages- 2 - Question 29

Which one of the following languages over the alphabet 0,1 is regular?

Detailed Solution for Test: Regular Expressions & Languages- 2 - Question 29

L = { 0^ m2  : m>= 3}

Now, in L* if we can generate 9 continuous powers of zero, then further every power can be generated by concatenating  09.

Here , L = {09 ,016, 025 , ...}

So, here are 9 continuous powers:

0120 : 016 016 016 09 09 09 09 09 09 09 09

0126 : 018018018018018018018    {018 can be generated as 09 09 }

Now, 0129  can be given as 0120 09 and so on..
Every Further powers can be generated by concatenating  09.

Test: Regular Expressions & Languages- 2 - Question 30

Identify the regular expression which represents the language containing all strings of a's and b's where each string contains at least two b's

Detailed Solution for Test: Regular Expressions & Languages- 2 - Question 30

 

Use Code STAYHOME200 and get INR 200 additional OFF
Use Coupon Code
Information about Test: Regular Expressions & Languages- 2 Page
In this test you can find the Exam questions for Test: Regular Expressions & Languages- 2 solved & explained in the simplest way possible. Besides giving Questions and answers for Test: Regular Expressions & Languages- 2, EduRev gives you an ample number of Online tests for practice