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

https://gateoverflow.in/93981/Half-l

check this:)

---

https://viterbi-web.usc.edu/~breichar/teaching/2011cs360/half(L)example.pdf

---

@Deepak Poonia Sir please explain this

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

please explain... III.suffix (L) part

---

@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

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.