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

I believe answer should be (C)

For option IV we only need to check whether string is of even length because if it is we can always break it in equal parts such that whole string belongs to the class of  Finite automata.

For that we need not to check other things . For every symbol we only make transitions b/w two states.

---

Sir how would we go about designing algorithm for making DFA for the "HALF" operation? 
Like for Prefix operation, we would set all the states that are on the way to the final state as final. The is a generalized algorithm that I can apply to any case of DFA and have a DFA for it's prefix operation. 

Is there an algorithm at all for the HALF operation?
How would you design the DFA for HALF(L) where L={ab^n | n>=1} 
Cc: @Praveen Saini @Arjun @srestha  

---

That should be in most books. You can see here too:

http://www-bcf.usc.edu/~breichar/teaching/2011cs360/half(L)example.pdf

---

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)

---

What do you mean by “projection in the first coordinate”?

---

Exercise 4.2.8: Let $L$ be a language. Define $half(L)$ to be the set of first halves of strings in $L$, that is $\{w| \text{ for some $x$ such that $|x|=|w|$. we have $wx$ in $L$}\}$. Prove that if $L$ is a regular language, so is $half(L)$.

[Introduction to automata theory, languages and computation- Ullman et. al]

---

Proof: Let $A$ be a DFA for $L$. We construct DFA $B$ for $half(L)$. The state of $B$ is of the form $[q,S]$, where:

 

• $q$ is the state A would be in after reading whatever input $B$ has read so far.

   

• $S$ is the set of states of $A$ such that $A$ can get from exactly these states to an accepting state by reading any input string whose length is the same as the length of the string $B$ has read so far.

It is important to realize that it is not necessary for $B$ to know how many inputs it has read so far; it keeps this information up-to-date each time it reads a new symbol. The rule that keeps things up to date is:

$$\delta_B([q,S],a) = [\delta_A(q,a),T]$$, where $T$ is the set of states $p$ of $A$ such that there is a transition from $p$ to any state of $S$ on any input symbol. In this manner, the first component continues to simulate $A$, while the second component now represents states that can reach an accepting state following a path that is one longer than the paths represented by $S$.

To complete the construction of $B$, we have only to specify:

 

• The initial state is $[q_0,F]$, that is, the initial state of $A$ and the accepting states of $A$. This choice reflects the situation when $A$ has read $0$ inputs: it is still in its initial state, and the accepting states are exactly the ones that can reach an accepting state on a path of length $0$.

   

• The accepting states of $B$ are those states $[q,S]$ such that $q$ is in $S$. The justification is that it is exactly these states that are reached by some string of length $n$, and there is some other string of length $n$ that will take state $q$ to an accepting state. $\square$

---

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.