GATE IT 2006 | Question: 80

Question

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

1. repeat $(L) = \{ww \mid  w \in  L\}$
2. prefix $(L) = \{u \mid ∃v : uv \in L\}$
3. suffix $(L) = \{v \mid  ∃u : uv \in L\}$
4. half $(L) = \{u \mid ∃v : | v | = | u | \text{ and } uv \in 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

Comments

didn't get option  4 is it asking no. of v = no. of u ?

---

"I think this solution 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." 
Automata | Prove that if $L$ is regular than $half(L)$ is regular too - Mathematics Stack Exchange

---

@jeets  yes , the length of V = the length of U (they are not asking the same number of symbol contain in u and v)
in these we create a finite automato that accept the even length. of string

Answer 1

Correct answer is B. Only $I$.

Repeat $(L) = \{ww \mid w \in L\}$ is non regular language

Half$(L)$, suffix$(L)$, and prefix$(L)$ are regular languages

Reference:

https://gateoverflow.in/3637/gate2006-it_81

Comments

@raja11sep , We can create FA for accepting all the suffixes of a string in Language on = {0,1} !

NFA will be: each state will have “∈” transition from initial state to that state!

---

@jiminpark thanks

---

I’m confused about half(L). It feels like to check whether a string is in half(L), we’d need to know the full length and then accordingly traverse to the half to get the length of u equal to v, which sounds like we need memory so how half(L) is regular ?

Answer 2

• 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
• so answer is B

Comments

|v|=|u| in half(l)

As given L is regular, we can do finite counting. Is this the justification for this?  

---

@ tusharp no its not :

If L is regular we can do finite counting its not true (Eg: L={aⁿ | n is even and n>=0} here L is is regular but not finite )

for |v|=|u| in half(L) 
Here we can give contradiction that 
L=(0+1)*

u=even length

v=odd length

uv=L

so it's regular.

Answer 3

Let $L$ be a regular language. We examine the four constructions to determine which may produce a non-regular language.

I. $\text{repeat}(L) = { ww \mid w \in L }$

This operation is not closed under regular languages. Take $L = {a,b}^*$, which is regular. Then

$$
\text{repeat}(L) = { ww \mid w \in {a,b}^* }.
$$

This language is not regular: a finite automaton cannot verify that the first half of the input equals the second half. By the Myhill–Nerode theorem, the strings $a^i$ and $a^j$ (for $i \neq j$) are distinguishable using the suffix $a^i$, yielding infinitely many equivalence classes.Hence, I can yield a non-regular language.

 

II. $\text{prefix}(L) = { u \mid \exists v : uv \in L }$

Regular languages are closed under prefix. Given a DFA for $L$, making all states reachable from the start state accepting yields a DFA for $\text{prefix}(L)$.
Thus, II always produces a regular language.

 

III. $\text{suffix}(L) = { v \mid \exists u : uv \in L }$

Regular languages are closed under suffix. An NFA for $\text{suffix}(L)$ is obtained by adding $\varepsilon$-transitions from a new start state to every state of a DFA for $L$, preserving the original final states. Therefore, III always yields a regular language.

 

IV. $\text{half}(L) = { w \mid \exists v : |v| = |w| \text{ and } wv \in L }$

This operation preserves regularity.
Although it may appear to require unbounded memory, a finite automaton can recognize $\text{half}(L)$ by simulating the original DFA on $w$ while simultaneously tracking, via a product construction, whether there exists a path of length $|w|$ from the resulting state to an accepting state. (boils down to even length string) 
Equivalently, one can construct an NFA that guesses the second half $v$ symbol-by-symbol in lockstep with reading $w$, using nondeterminism to verify that $wv \in L$.
This construction is standard and confirms that IV always yields a regular language.

For example, if $a^*b^*$, then $\text{half}(L) = a^*b^*$ if $L = \Sigma^*$, then $\text{half}(L) = \Sigma^*$; in all cases, the result is regular.

 

$$
\boxed{\text{B. Only I}}
$$

Answer 4

Hope you have understand

Comments

so option B is correct