GATE IT 2006 | Question: 81

Question

Let $L$ be a regular language. Consider the constructions on $L$ below:

1. $\text{repeat} (L) = \{ww \mid w \in L\}$
2. $\text{prefix} (L) = \{u \mid \exists v : uv \in L\}$
3. $\text{suffix} (L) = \{v \mid \exists u: uv \in L\}$
4. $\text{half} (L) = \{u \mid \exists v: | v | = | u | \text{ and } uv \in L\}$

Which of the constructions could lead to a non-regular language?

1. Both I and IV
2. Only I
3. Only IV
4. Both II and III

Which choice of $L$ is best suited to support your answer above?

• A. $(a + b)^*$
• B. $\{\epsilon, a, ab, bab\}$
• C. $(ab)^*$
• D. $\{a^nb^n \mid n \geq 0\}$

Comments

Other part

https://gateoverflow.in/3624/gate2006-it-80

Answer 1

1. $\text{repeat}(L)$ is non regular
   http://www.cs.odu.edu/~toida/nerzic/390teched/regular/reg-lang/non-regularity.html [example 2]
2. $\text{prefix}(L)$ is regular
   http://www.public.asu.edu/~ccolbou/src/355hw2sols09.pdf [2(a)]
3. $\text{suffix}(L)$ is regular
   http://www.public.asu.edu/~ccolbou/src/355hw2sols09.pdf [2(b)]
4. $\text{half}(L)$ is regular
   https://math.stackexchange.com/questions/1539658/automata-prove-that-if-l-is-regular-than-halfl-is-regular-too 

So, in first part of question, option B is correct only (i).

For second part of question:

A is answer.

• For option $B$  $L = \{\epsilon, a, ab, bab\}$ , $\text{repeat}(L) = \{ \epsilon, aa,abab, babbab\}$ is regular. So, not a suitable example.
• For option C, regular expression for Repeat(L) will be $(abab)^*$ and hence regular. So, this also is not a suitable example.
• For option D, $L$ it self is not regular and hence it can not be the answer. 
• For A, all strings of $\text{repeat(L)}$ is in $L.$ But that does not mean $\text{repeat}(L)$ is regular. For that we also have to ensure all strings in $L$ is in $\text{repeat(L)}$ which is not the case (or all strings not in $\text{repeat(L)}$ is not in $L).$ $\text{repeat(L)}$ here is $\{ww\mid w\in (a+b)^*\}$ which is actually not even context-free.

Comments

The question starts with "Let L be a regular language".

This makes us to eliminate option (d) because it is not regular this won't be our choice of L.

 

---

Proof for Half(L):

The solution of Half(L) is the projection of the cross product of two NFAs. One is the actual NFA accepting L. Another one is the reverse NFA i.e. the NFA of L with arrows in the opposite direction, along with a new state which acts as the starting state and such that you can reach any state in F just by the empty string. After taking the cross product you declare the final state as the diagonal elements i.e. states of the fo (d,d). Then if (x,y) is accepted by this NFA x.(-y) is accepted by the DFA of L where (-y) is the reverse of y. The answer is the projection in the first coordinate.

(source: https://math.stackexchange.com/a/1539751/545704 ArkaGhosh's comment)

---

Nice question

Answer 2

A.repeat (L) = {ww | w ∊ L}   //CSL so non-regular Hence Answer is OptionA

B.prefix (L) = {u | ∃v : uv ∊ L}//can be realized by making NFA where all the states are final states.

i.e. L={abc} then Prefix(L)={^,a,ab,abc} 

C.suffix (L) = {v | ∃u uv ∊ L}

suffix(L)=Reverse(prefix(Reveres(L))) //we know reverse and prefix closed under regular Hence suffix(L) also regular

i.e. L={abc} then suffix(L)={^,c,bc,abc} 

D.half (L) = {u | ∃v : | v | = | u | and uv ∊ L}//https://gateoverflow.in/93981/half-l //Hence Regular

So option A is Ans

Comments

hey @ Rajesh Pradhan see this ..... "suffix(L)=Reverse(prefix(Reveres(L))) //we know reverse and prefix closed under regular Hence suffix(L) also regular

i.e. L={abc} then Prefix(L)={^,c,bc,abc} ".

i think ,Here it will be suffix not prefix.

Answer 3

• repeat(L) should not be confused with concatenation as there is a specific order to it. Only same strings are concatenated with each other and not all. Moreover, double word language is not even a CFG [non-regular].
• prefix(L) is a regular language – all the states in L’s DFA could be made final, giving result to a DFA which would accept prefix(L) [regular]
• suffix(L) is a regular language as a NFA could be constructed which would accept suffix(L). Every state in L’s DFA can get an incident # – edge from start state – this NFA would accept suffix(L) [regular].
• half(L) is a regular language. It is just a language containing even length strings
• from above repeat could lead to non-regular language
• so we should choose option such that it should be regular and it should not follow repeat
• since L should be regular mention in question . so we can eliminate option d.
• option c if we repeat it can be (abab)* .even if we repeat it is regular so it is not answer.
• option b since it is finite even if we repeat still it is regular so it is not answer.
• so answer for this question is option A

Comments

I would like to addd two corrections in this explanation:

1.  In PREFIX(L) ,If considering DFA then those states should not be made final which are Deadstate. Ex; L={starting with a } over {a,b}. Now ,if you make deadstates too as final then string 'b' will be selected which is wrong because 'b' will never come in PREFIX(L). Note: If you take NFA of L,then can say to make all states as final.
2.  In HALF(L)..,I think your explanation is not complete since  it would accept to those even-length strings which are not in L.

Answer 4

I think option C).
Let me know the correct answer?

Comments

In question it is asked which condition can lead to a Non-regular language, and D is supporting that condition. Why it is wrong and what is the correct answer then?

---

In the previous part of this question answer seems to be (C) which I have added there.

Now coming to this question, we need a language in which we can't detect a string to be such that L(M)={ ww | w is in L }

(D) it can never generate such a language other than "empty" language and so it is trivially TRUE since it never  generates required language.

(C) This option can generate the language L(M)={ ww | w is in L } using Finite automata.What we need it only allow EVEN no of iterations of it. So it does not prove us right.

(B ) This is a finit language hence trivially Regular .for this we can always check using FA whether L(M)={ ww | w is in L } is in L

(A) This option is that supports our assumption. Let's see how ??

With this we can construct a DFA that accepts everything. Since FA is possible ,it is Regular.But see for the same we can't check whether L(M)={ ww | w is in L } is in L ?? So this supports our assumption that L(M)={ ww | w is in L } can't be checked with an FA and this is one of the example of language that IN SPITE OF BEING REGULAR CAN'T CHECK FOR L(M)={ ww | w is in L } 

If anything wrong,please comment !!

---

@ Sandeep_Uniyal can u carify your points?