Half(L)

Question

If L is Regular Language then

half (L) = {u | ∃v : | v | = | u | and uv ∊ L} is also Regular Language.

Can anyone plz explain this with simple example.

Answer 1

Language $L$ may contain both even and odd length strings. half(L) takes/contains first half of even length strings of Language $L$ ( $|u| = |v|$ is possible only if string $uv \in L$ is of even length.)

So, we proceed further and take every even length string of language $L$ and put it's first half in some other set (or) Language.

If $L$ is a finite lanuage, then definitely new formed language is also finite and is thus Regular.

And if it is infinite, and is Regular, So, there exists a FA for that. So, strings formed by taking first half must reach some state in between intial and final state. And we need to modify some states to accept that language.

Another way i could think of is, If $L$ is regular, then RegExp exists, and RegExp for half(L) will surely be prefix of RegExp of $L$, and If we are able to give some RegExp, then we can say it is Regular. (But, Cann't comeup with a formal proof)

• $L = a^*$ , then half(L) $= a^*$
• $L = a(aa)^*$, then half(L) $= \phi$
• $L = a^*b^*$, then half(L) $= a^*b^*$

Comments

FA has no memory, so how we are getting half of the string ..?? not getting this point... :(

---

@rishu_darkshadow 

We don't require memory for this. Draw all the cases and you will get "all even length strings" as the language.

---

@Kabir5454 @Abhrajyoti00 @gate

How half of 

a*b* is a*b*.

a(aa)* half if fie.

What does half exactly mean here.

The actual question present in 

https://gateoverflow.in/3624/gate-it-2006-question-80

Answer 2

Half(L) - DFA for L is given.

Construction of DFA for Half(L):

If 'w' takes us to state in end 'q', we accept 'w' if we have 'x' such that |x| = |w| and takes us to final state.

We add extra information to each state - the number of steps to reach final state. If we reach a state after 'n' moves in original DFA for L, we also save in 'q' the set of states after 'n' moves from the final state.

All states which will reach final state in 1,2,3...n steps are stored within each state. When a particular state has itself among the saved states that state is the final state for Half(L). This way we will get the new final state for Half(L).
Source: GO Classroom

Comments

but how can we save any info in finite automata about the path the string traversed or the no of steps.?

finite automata cannot store or save anything right?

Answer 3

let L' = H(L)

let q0,q1,...qn be the states of DFA D that recognizes L

Machine of first kind -:

we're going to construct N DFA's similar to D, except each starts at  qi (all previous states deleted)

Machine of second kind -:

we're going to construct N more DFA's each starting at qi state (all previous states deleted) and each edge has sigma symbol (i.e take any symbol, but take one and only one) and has only one accepting state at qi.

Assembly -:

(Note that we have N machines of each kind, so total of 2N machines) We do the following for i-th machine of each kind -:

    We take a string pass it in 2nd machine to to see if it comes at qi at the end of the input.
    If it does, we take the string and pass it in first machine and check if it accepts the string.

    If both accept, then we accept. othwise we move to next iteration.

(basically this machine is the union of intersections, i.e (M1 & M'1) + (M2 & M'2) + ... so on (+ is union, & is intersection)

This way we have created a machine that accepts all half string that end at state qi for all i's.
Therefore the whole contraption accepts the Half(L).