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?
Both I and II
| |
II only | |
Neither I nor II | |
I only
|
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?
Every finite subset of a non-regular set is regular | |
Every subset of a regular set is regular | |
Every finite subset of a regular set is regular | |
The intersection of two regular sets is regular |
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)
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?
Only L1 and L2 | |
Only L2, L3 and L4 | |
Only L3 and L4 | |
Only L3 |
⇒ 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.?
Only S2is true. | |
Both S1and S2are true. | |
Only S1is true. | |
Neither S1nor S2is true. |
-
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?
Both I and IV | |
Only I | |
Only IV | |
Both II and III |
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 + b)* | |
{ϵ, a, ab, bab} | |
(ab)* | |
{anbn | n ≥ 0} |
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.
True | |
False |
Question 9 |
All subsets of regular sets are regular.
True | |
False |
Question 10 |
Choose the correct alternatives (More than one may be correct). Let R1 and R2 be regular sets defined over the alphabet Σ Then:
R1 ∩ R2 is not regular. | |
R1 ∪ R2 is regular. | |
Σ* − R1 is regular. | |
R1* is not regular. | |
Both (B) and (C). |
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}
L1 and L3 only | |
L2 only | |
L2 and L3 only | |
L3 only |
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 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?
Both P and Q are true | |
P is true and Q is false | |
P is false and Q is true | |
Both P and Q are false
|
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?
{anbm |n,m ≥ 0} | |
{w ∈ {a,b}* | w has equal number of a’s and b’s} | |
{an |n ≥ 0}∪{bn |n ≥ 0}∪{an b(sup>n|n ≥ 0} | |
{a,b}* |
Question 14 |
If L is a regular language over Σ = {a,b}, which one of the following languages is NOT regular?
Suffix (L) = {y ∈ Σ* such that xy ∈ L} | |
{wwR │w ∈ L} | |
Prefix (L) = {x ∈ Σ*│∃y ∈ Σ* such that xy ∈ L} | |
L ∙ LR = {xy │ x ∈ L, yR ∈ L} |
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?
3 | |
9 | |
5 | |
24 |
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.