Regular-Language

Question 1

Consider the following statements.

    I. If L1 ∪ L2 is regular, then both L1 and L2 must be regular.
    II. The class of regular languages is closed under infinite union.

Which of the above statements is/are TRUE?

A
Both I and II
B
II only
C
Neither I nor II
D
I only
Question 1 Explanation: 
Statement I is wrong.
Assume L1 = {an bn | n>0} and L2 = complement of L1
L1 and L2 both are DCFL but not regular, but L1 U L2 = (a+b)* which is regular.
Hence even though L1 U L2 is regular, L1 and L2 need not be always regular.
Statement II is wrong.
Assume the following finite (hence regular) languages.
L1 = {ab}
L2 = {aabb}
L3 = {aaabbb}
.
.
.
L100 = {a100 b100}
.
.
.
If we take infinite union of all above languages i.e,
{L1 U L2 U ……….L100 U ……}
then we will get a new language L = {an bn | n>0}, which is not regular.
Hence regular languages are not closed under infinite UNION.
Question 2

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
Question 2 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 3

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

Consider the following languages:

    L1 = {ww|w ∈ {a,b}*}
    L2 = {wwR|w ∈ {a,b}*, wR is the reverse of w}
    L3 = {02i|i is an integer}
    L3 = {0i2|i is an integer}

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
Question 4 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 5
  • Consider the following two statements about regular languages:
    S1: Every infinite regular language contains an undecidable language as a subset.
    S2: Every finite language is regular.
    Which one of the following choices is correct.?
A
Only S2is true.
B
Both S1and S2are true.
C
Only S1is true.
D
Neither S1nor S2is true.
Question 5 Explanation: 
  • S1 is true. We can solve this intuitively.

    Suppose L=(a+b)*  i.e, sigma* 

    We know that this is a regular language and any language is subset of this language.

     

    As we know so many undecidable languages (not recursive languages) exist, hence S1 is true.

    Take another example:

     

    L=a* which is regular and infinite.

    Take its subset L1=an | n> 0 and n is a set such that it cannot be generated by any algorithm

     

    I.e, n is a set of natural numbers which does not have any algorithm which can generate this

     

    So  L1 is a undecidable language.

     

    L2 is true as every finite language is regular.

Question 6

Let L be a regular language. Consider the constructions on L below:
I. repeat (L) = {ww | w ∊ L}
II. prefix (L) = {u | ∃v : uv ∊ L}
III. suffix (L) = {v | ∃u : uv ∊ L}
IV. half (L) = {u | ∃v : | v | = | u | and uv ∊ L}
Which of the constructions could lead to a non-regular language?

A
Both I and IV
B
Only I
C
Only IV
D
Both II and III
Question 6 Explanation: 
Repeat(L) = {ww|w ∈ L} is non-regular language.
Half (L), Suffix (L) and Prefix (L) are regular languages.
Question 7

Let L be a regular language. Consider the constructions on L below:
(I) repeat (L) = {ww | w ∊ L}
(II) prefix (L) = {u | ∃v : uv ∊ L}
(III) suffix (L) = {v | ∃u uv ∊ L}
(IV) half (L) = {u | ∃v : | v | = | u | and uv ∊ L}
Which choice of L is best suited to support your answer above?

A
(a + b)*
B
{ϵ, a, ab, bab}
C
(ab)*
D
{anbn | n ≥ 0}
Question 7 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 8

Regularity is preserved under the operation of string reversal.

A
True
B
False
Question 8 Explanation: 
Regular language is closed under reversal.
Question 9

All subsets of regular sets are regular.

A
True
B
False
Question 9 Explanation: 
a*b* is regular but its subset anbn is not regular.
Question 10

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

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).
Question 10 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 11

Which of the following language is/are regular ?

    L1: {wxwR ⎪ w, x ∈ {a, b}* and ⎪w⎪, ⎪x⎪ >0} wR is the reverse of string w
    L2: {anbm ⎪m ≠ n and m, n≥0}
    L3: {apbqcr ⎪ p, q, r ≥ 0}
A
L1 and L3 only
B
L2 only
C
L2 and L3 only
D
L3 only
Question 11 Explanation: 
L1: 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.
L2: In this number of a's is dependent on number of b's. So PDA is needed.
L3: Any number of a's followed by any number of b's followed by any number of c's. Hence Regular.
Question 12
Language L1 is defined by the grammar: S1 → aS1b|ε
Language L2 is defined by the grammar: S2 → abS2
Consider the following statements:
P: L1is regular
Q: L2is 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
Question 12 Explanation: 
The language L1 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, L1 is not regular.
Moreover, L1 = {an bn | n ≥ 0} which is DCFL.
The language L2 generated by grammar contains repetition of “ab” i.e. L2 = (ab)* which is clearly a regular language.
Question 13

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

S→ aS|bS|ε
A
{anbm |n,m ≥ 0}
B
{w ∈ {a,b}* | w has equal number of a’s and b’s}
C
{an |n ≥ 0}∪{bn |n ≥ 0}∪{an b(sup>n|n ≥ 0}
D
{a,b}*
Question 13 Explanation: 
From the given grammar we can draw the DFA,
Question 14

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
{wwR │w ∈ L}
C
Prefix (L) = {x ∈ Σ*│∃y ∈ Σ* such that xy ∈ L}
D
L ∙ LR = {xy │ x ∈ L, yR ∈ L}
Question 14 Explanation: 
wwR cannot be recognized without using stack, so it cannot be regular.
Question 15

For Σ = {a,b}, let us consider the regular language L = {x|x = a2+3k or x = b10+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
Question 15 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: uviw ∈ L
We have to find "n" which satisfies for all the strings in L.
Considering strings derived by b10+12k.
The minimum string in L = "bbbbbbbbbb" but this string b10 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.
There are 15 questions to complete.

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

Register Now

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