Regular language

Question 1
Which of the following is TRUE?
A
Every subset of a regular set is regular.
B
Every finite subset of a non-regular set is regular.
C
The union of two non-regular sets is not regular.
D
Infinite union of finite sets is regular.
       Theory of Computation        Regular Language       Gate-2007
Question 1 Explanation: 
If a set is finite then it must be regular , as every language which contains finite elements is regular. Hence, every finite subset of a non-regular set is regular.
Every subset of regular set is regular, is false. For example L = {an bn | n ≥ 0} is subset of ∑* and L is CFL, whereas ∑* is regular. Hence, every subset of regular set need not be regular.
The union of two non-regular sets is not regular, is also a false statement.
For example, consider two CFL’s.
L = {an bn | n ≥ 0} and its complement Lc = {am bn | m ≠ n } U b*a*.
If we take UNION of L and Lc , we will get ∑*, which is regular. Hence the UNION of two non-regular set may or may not be regular.
The statement, Infinite union of finite sets is regular is also a false statement.
Question 2
Which of the following languages is regular? 
A
{wwR|w ∈ {0,1}+}
B
{wwRx|x, w ∈ {0,1}+}
C
{wxwR|x, w ∈ {0,1}+}
D
{xwwR|x, w ∈ {0,1}+}
       Theory of Computation        Regular Language       Gate-2007
Question 2 Explanation: 
The regular expression corresponding to option C is:
0 (0+1)+ 0 + 1 (0+1)+ 1
Any string which begins and ends with same symbol, can be written in form of “wxwr
For example consider a string: 10010111, in this string “w=1” , “x= 001011” and wr = 1. Hence any string which begins and ends with either “0” or with “1” can be written in form of “wxwr” and L={wxwr | x,w ϵ {0,1}+ } is a regular language.
Question 3
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?
A
L = {s ∈ (0+1)* | n0(s) is a 3-digit prime}
B
L = {s ∈ (0+1)* | for every prefix s' of s,|n0(s') - n1(s')| ≤ 2}
C
L = {s ∈ (0+1)* |n0(s) - n1(s)| ≤ 4}
D
L = {s ∈ (0+1)* | n0(s) mod 7 = n1(s) mod 5 = 0}
       Theory of Computation        Regular language       Gate-2006
Question 3 Explanation: 
Since 3-digit prime numbers are finite so language in option A is finite, hence it is regular.
Option B: The DFA contains 6 states
State1: n0(s') - n1(s') = 0
State2: n0(s') - n1(s') = 1
State3: n0(s') - n1(s') = 2
State4: n0(s') - n1(s') = -1
State5: n0(s') - n1(s') = -2
State6: Dead state (trap state)
Hence it is regular.
Option D: Product automata concept is used to construct the DFA.
mod 7 has remainders {0,1,2,3,4,5,6} and mod 5 remainders {0,1,2,3,4}
So product automata will have 35 states.
But option C has infinite comparisons between number of 0’s and 1’s.
For ex: n0(s) = 5 and n1(s) = 1 then n0(s) - n1(s) = 4 and if n0(s) = 15 and n1(s) = 11 then n0(s) - n1(s) = 4.
Hence this is CFL.
Question 4
   
A
Both I and IV
B
Only I
C
Only IV
D
Both II and III
       Theory of Computation        Regular Language       Gate 2006-IT
Question 4 Explanation: 
Repeat(L) = {ww|w ∈ L} is non-regular language.
Half (L), Suffix (L) and Prefix (L) are regular languages.
Question 5
 
A
(a + b)*
B
{ϵ, a, ab, bab}
C
(ab)*
D
{anbn | n ≥ 0}
       Theory of Computation        Regular Language       Gate 2006-IT
Question 5 Explanation: 
A counter example which proves all the conclusions of the last question in one go should have the following properties:
1) L should be regular due to demand of question.
2) L should be an infinite set of strings.
3) L should have more than one alphabet in its grammar, otherwise repeat(L) would be regular.
∴ (a + b)* is the perfect example to support the conclusions of last questions.
Question 6
Which of the following statements is false?
A
Every finite subset of a non-regular set is regular
B
Every subset of a regular set is regular
C
Every finite subset of a regular set is regular
D
The intersection of two regular sets is regular
       Theory of Computation        Regular Language       Gate-1998
Question 6 Explanation: 
Let regular language L = a*b* and subset of L is anbn, n ≥ 0, which is not regular. Hence option (B) is false.
Question 7
   
A
Only L1 and L2
B
Only L2, L3 and L4
C
Only L3 and L4
D
Only L3
       Theory of Computation        Regular Language       Gate-2001
Question 7 Explanation: 
L1 = {ww|w∈{a,b}*}
⇒ This is not regular language. We can't be able to identify where the 'w' will ends and where the next 'w' starts.
L2 = {wwR|w∈{a,b}*, wR is the reverse of w}
⇒ This also not a regular language. We can't identify where 'w' ends.
L4 = {0i2|i is an integer}
= {0i*0i|i is an integer}
⇒ This is also not a regular language. We can't identify where 0i ends.
L3 = {02i|i is an integer}
⇒ This is regular. We can easily find whether a string is even or not.
Question 8
 
A
R1 ∩ R2 is not regular.
B
R1 ∪ R2 is regular.
C
Σ* − R1 is regular.
D
R1* is not regular.
E
Both (B) and (C).
       Theory of Computation        Regular Language       Gate-1990
Question 8 Explanation: 
Regular languages are closed under,
1) Intersection
2) Union
3) Complement
4) Kleen-closure
Σ* - R1 is the complement of R1.
Hence, (B) and (C) are true.
Question 9
Regularity is preserved under the operation of string reversal.
A
True
B
False
       Theory of Computation        Regular Language       GATE-1987
Question 9 Explanation: 
Regular language is closed under reversal.
Question 10
All subsets of regular sets are regular.
A
True
B
False
       Theory of Computation        Regular Language       GATE-1987
Question 10 Explanation: 
a*b* is regular but its subset anbn is not regular.
There are 10 questions to complete.