Log In
13 votes
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.
in Theory of Computation
retagged by

2 Answers

20 votes

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^*$
Thank U @mcjoshi
can anyone clear this points !?
FA has no memory, so how we are getting half of the string ..?? not getting this point... :(


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

1 vote
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

Related questions

4 votes
1 answer
The tail of a language is the set of all suffixes of its strings, that is tail(L) = {y : xy ∈ L for some x ∈ Σ ∗ }. How do I show that the family of regular languages is closed under this operation.
asked Oct 9, 2017 in Theory of Computation Garrett McClure 361 views
2 votes
1 answer
Let L be any regular language on Σ = {a, b}. Show that an algorithm exists for determining if L contains any strings of even length.
asked Oct 4, 2017 in Theory of Computation Garrett McClure 179 views
1 vote
3 answers
We can say there are four types of strings in the language so the regex will be: a(a+b)+a + b(a+b)+b + a(a+b)+b + b(a+b)+a Please expleain where I am wrong
asked Jul 26, 2017 in Theory of Computation Durgesh Singh 1.6k views
0 votes
2 answers
We know, here R subset L so by formula R intersection L= R, but for any string R=L( both language are same) R intersection L can be R or L? Correct me!
asked Jan 12, 2017 in Theory of Computation smartmeet 206 views