GATE Computer Science Engineering(CSE) 2027 Test: Regular Expressions

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.

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.

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 0ⁿ1ⁿ is not regular

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

And L1 = aⁿbⁿ which is CFL but not regular.

And here L1 is subset of L2.

Contradiction for B. Let L1 = ab ,

which is regular. And L2 = aⁿbⁿ which is CFL but not regular.

And here L1 is subset of L2.

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

is Regular having regular expression  (ab)*.

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

B,C are true

(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. 

 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.

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.

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 = { aⁿ b^m | n > m }. which is not regular.
Correction:I think c should be that x has more a's than b's.

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

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

 Linear Power and regular expression can be stated as

  non linear power So CSL

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. 

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.

correct answer is B. only 1 .

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

(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 = {0ⁱ1ⁱ | i ∊ N}, which is not regular. So, D is false. 

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]

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.

c)complement of regular Language is regular

  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*

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 {∈}.

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

(Also, since both L₁ and L₂ are Regular, their concatenation has to be Regular since Regular languages are closed under concatenation)

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

L3 is simple to guess, it is regular. Below is DFA for L1.

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.

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 

if it start with 1 it goes to final state

if start with 0 it will go to the reject state

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  0⁹.

Here , L = {0⁹ ,0¹⁶, 0²⁵ , ...}

So, here are 9 continuous powers:

0¹²⁰ : 0¹⁶ 0¹⁶ 0¹⁶ 0⁹ 0⁹ 0⁹ 0⁹ 0⁹ 0⁹ 0⁹ 0⁹

0¹²⁶ : 0¹⁸0¹⁸0¹⁸0¹⁸0¹⁸0¹⁸0¹⁸    {0¹⁸ can be generated as 0⁹ 0⁹ }

Now, 0¹²⁹  can be given as 0¹²⁰ 0⁹ and so on..
Every Further powers can be generated by concatenating  0⁹.