topic - solutions adda

Regular-Language

Please wait while the activity loads.
If this activity does not load, try refreshing your browser. Also, this page requires javascript. Please visit using a browser with javascript enabled.

If loading fails, click here to try again

Question 1

If L is a regular language over Σ = {a,b}, which one of the following languages is NOT regular?

A	Suffix (L) = {y ∈ Σ* such that xy ∈ L}
B	{ww^R │w ∈ L}
C	Prefix (L) = {x ∈ Σ│∃y ∈ Σ such that xy ∈ L}
D	L ∙ L^R = {xy │ x ∈ L, y^R ∈ L}

Theory-of-Computation Regular-Language GATE 2019 Video-Explanation

Question 1 Explanation:

ww^R cannot be recognized without using stack, so it cannot be regular.

Question 2

For Σ = {a,b}, let us consider the regular language L = {x|x = a^2+3k or x = b^10+12k, k ≥ 0}. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for L?

A	3
B	9
C	5
D	24

Theory-of-Computation Regular-Language GATE 2019 Video-Explanation

Question 2 Explanation:

Pumping Lemma for Regular Languages:
For any language L, there exists an integer n, such that for all x ∈ L with |x| ≥ n, there exists u,v, w ∈ Σ*, such that x = uvw, and
(1) |uv| ≤ n
(2) |v| ≥ 1
(3) for all i ≥ 0: uvⁱw ∈ L
We have to find "n" which satisfies for all the strings in L.
Considering strings derived by b^10+12k.
The minimum string in L = "bbbbbbbbbb" but this string b¹⁰ cannot be broken in uvw.
So, pumping length 3, 9 and 5 cannot be the correct answer.
So, the minimum pumping length, such that any string in L can be divided into three parts "uvw" must be greater than 10.

Question 3

Which of the following languages is generated by the given grammar?

S→ aS|bS|ε

A	{aⁿb^m \|n,m ≥ 0}
B	{w ∈ {a,b}* \| w has equal number of a’s and b’s}
C	{aⁿ \|n ≥ 0}∪{bⁿ \|n ≥ 0}∪{aⁿ b(sup>n\|n ≥ 0}
D	{a,b}*

Theory-of-Computation Regular-Language GATE 2016 [Set-1] Video-Explanation

Question 3 Explanation:

From the given grammar we can draw the DFA,

Question 4

Language L₁ is deﬁned by the grammar: S₁ → aS₁b|ε
Language L₂ is deﬁned by the grammar: S₂ → abS₂|ε
Consider the following statements:
P: L₁is regular
Q: L₂is regular
Which one of the following is TRUE?

A	Both P and Q are true
B	P is true and Q is false
C	P is false and Q is true
D	Both P and Q are false

Theory-of-Computation Regular-Language GATE 2016 [Set-2] Video-Explanation

Question 4 Explanation:

The language L₁ generated by the grammar contains equal number of a’s and b’s, but b’s comes after a’s.
So, in order to compare equality between a’s and b’s memory (stack) is required.
Hence, L₁ is not regular.
Moreover, L₁ = {aⁿ bⁿ | n ≥ 0} which is DCFL.
The language L₂ generated by grammar contains repetition of “ab” i.e. L₂ = (ab)* which is clearly a regular language.

Question 5

Which of the following language is/are regular ?

ⁿ

A	L₁ and L₃ only
B	L₂ only
C	L₂ and L₃ only
D	L₃ only

Theory-of-Computation Regular-Language GATE 2015 [Set-2]

Question 5 Explanation:

L₁: All strings of length 3 or more with same start and end symbol, as everything in middle is consumed by x as per the definition.
L₂: In this number of a's is dependent on number of b's. So PDA is needed.
L₃: Any number of a's followed by any number of b's followed by any number of c's. Hence Regular.

Question 6

Let P be a regular language and Q be a context-free language such that Q ⊆ P. (For example, let P be the language represented by the regular expression p*q* and Q be [pⁿqⁿ | n ∈ N]). Then which of the following is ALWAYS regular?

A	P ∩ Q
B	P – Q
C	Σ* – P
D	Σ* – Q

Theory-of-Computation Regular-Language GATE 2011

Question 6 Explanation:

Exp: Σ* - P is the complement of P so it is always regular,
since regular languages are closed under complementation.

Question 7

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 7 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 = {aⁿ bⁿ | n ≥ 0} and its complement L^c = {a^m bⁿ | m ≠ n } U b*a*.
If we take UNION of L and L^c , 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 8

Which of the following languages is regular?

A	{ww^R\|w ∈ {0,1}⁺}
B	{ww^Rx\|x, w ∈ {0,1}⁺}
C	{wxw^R\|x, w ∈ {0,1}⁺}
D	{xww^R\|x, w ∈ {0,1}⁺}

Theory-of-Computation Regular-Language GATE 2007

Question 8 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 “wxw^r”
For example consider a string: 10010111, in this string “w=1” , “x= 001011” and w^r = 1.
Hence any string which begins and ends with either “0” or with “1” can be written in form of “wxw^r” and L = {wxw^r | x,w ϵ {0,1}⁺} is a regular language.

Question 9

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

A	L = {s ∈ (0+1)* \| n₀(s) is a 3-digit prime}
B	L = {s ∈ (0+1)* \| for every prefix s' of s,\|n₀(s') - n₁(s')\| ≤ 2}
C	L = {s ∈ (0+1)* \|n₀(s) - n₁(s)\| ≤ 4}
D	L = {s ∈ (0+1)* \| n₀(s) mod 7 = n₁(s) mod 5 = 0}

Theory-of-Computation Regular-Language GATE 2006

Question 9 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
State 1: n₀(s') - n₁(s') = 0
State 2: n₀(s') - n₁(s') = 1
State 3: n₀(s') - n₁(s') = 2
State 4: n₀(s') - n₁(s') = -1
State 5: n₀(s') - n₁(s') = -2
State 6: 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: n₀(s) = 5 and n₁(s) = 1 then n₀(s) - n₁(s) = 4 and if n₀(s) = 15 and n₁(s) = 11 then n₀(s) - n₁(s) = 4.
Hence this is CFL.

Question 10

Consider the following languages:

²ⁱ

^i²

Which of the languages are regular?

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 10 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 = {ww^R|w∈{a,b}*, w^R is the reverse of w}
⇒ This also not a regular language. We can't identify where 'w' ends.
L4 = {0^i²|i is an integer}
= {0ⁱ*0ⁱ|i is an integer}
⇒ This is also not a regular language. We can't identify where 0ⁱ ends.
L3 = {0²ⁱ|i is an integer}
⇒ This is regular. We can easily find whether a string is even or not.

Question 11

(a) Given that A is regular and A∪B is regular, does it follow that B is necessarily regular? Justify your answer.
(b) Given two finite automata M1, M2, outline an algorithm to decide if L(M1)⊆L(M2). (note: strict subset)

A	Theory Explanation.

Theory-of-Computation Regular-Language GATE 1999

Question 12

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 12 Explanation:

Let regular language L = a*b* and subset of L is aⁿbⁿ, n ≥ 0, which is not regular. Hence option (B) is false.

Question 13

Consider the following statements.

₁

₂

₁

₂

Which of the above statements is/are TRUE?

A	Both I and II
B	II only
C	Neither I nor II
D	I only

Theory-of-Computation Regular-Language GATE 2020 Video-Explanation

Question 13 Explanation:

Statement I is wrong.
Assume L₁ = {aⁿ bⁿ | n>0} and L₂ = complement of L₁
L₁ and L₂ both are DCFL but not regular, but L₁ U L₂ = (a+b)* which is regular.
Hence even though L₁ U L₂ is regular, L₁ and L₂ need not be always regular.
Statement II is wrong.
Assume the following finite (hence regular) languages.
L₁ = {ab}
L₂ = {aabb}
L₃ = {aaabbb}
.
.
.
L₁₀₀ = {a¹⁰⁰ b¹⁰⁰}
.
.
.
If we take infinite union of all above languages i.e,
{L₁ U L₂ U ……….L₁₀₀ U ……}
then we will get a new language L = {aⁿ bⁿ | n>0}, which is not regular.
Hence regular languages are not closed under infinite UNION.

Question 14

Choose the correct alternatives (More than one may be correct). Let R₁ and R₂ be regular sets defined over the alphabet Σ Then:

A	R₁ ∩ R₂ is not regular.
B	R₁ ∪ R₂ is regular.
C	Σ* − R₁ is regular.
D	R₁* is not regular.
E	Both (B) and (C).

Theory-of-Computation Regular-Language GATE 1990 Video-Explanation

Question 14 Explanation:

Regular languages are closed under,
1) Intersection
2) Union
3) Complement
4) Kleen-closure
Σ* - R₁ is the complement of R₁.
Hence, (B) and (C) are true.

Question 15

Regularity is preserved under the operation of string reversal.

A	True
B	False

Theory-of-Computation Regular-Language GATE 1987 Video-Explanation

Question 15 Explanation:

Regular language is closed under reversal.

There are 15 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access

A	{aⁿb^m \|n,m ≥ 0}
B	{w ∈ {a,b}* \| w has equal number of a’s and b’s}
C	{aⁿ \|n ≥ 0}∪{bⁿ \|n ≥ 0}∪{aⁿ b(sup>n\|n ≥ 0}
D	{a,b}*

A	{ww^R\|w ∈ {0,1}⁺}
B	{ww^Rx\|x, w ∈ {0,1}⁺}
C	{wxw^R\|x, w ∈ {0,1}⁺}
D	{xww^R\|x, w ∈ {0,1}⁺}

A	L = {s ∈ (0+1)* \| n₀(s) is a 3-digit prime}
B	L = {s ∈ (0+1)* \| for every prefix s' of s,\|n₀(s') - n₁(s')\| ≤ 2}
C	L = {s ∈ (0+1)* \|n₀(s) - n₁(s)\| ≤ 4}
D	L = {s ∈ (0+1)* \| n₀(s) mod 7 = n₁(s) mod 5 = 0}