1
$\begingroup$

Let $L$ be a regular language.

Define: $half(L)=\{x|xy\in L,|x|=|y|\}$

Prove that $half(L)$ is regular as well.

I have seen a hard proof by using the DFA A of L, building a NFA B (such that every transition from the stating state to the next one with the word $x$ will exist iff $\exists y$ s.t $|x|=|y| , \delta_A(q,y)\in F_A$).

Then using the product automaton of A and B to solve it.

I wonder if there is a easy proof for this one.

Thanks a lot!

$\endgroup$
1

3 Answers 3

2
$\begingroup$

If $L$ is regular , then FirstHalves or $Half(L)$ is also regular.

Algorithm:

  1. Design $DFA, M$ of language $L$

  2. Find the reversal of $DFA$ ,$M$ , say $N.$

  3. Traverse $M$ for one transition (for given $\Sigma$ ) and $N$ for one transition (for $\Sigma$ ) , and repeat the process.

  4. If We reach at common states, Mark them as New finals in $DFA$, $M$ (remove old final and do minimization )

  5. Result is $DFA$ of $Half(L)$ or $FirstHalve(L)$

[Note: In Short, design $DFA$ for $L,$ traverse from both directions (start and final),if reach at common states with same number of transitions, make them as new finals, result will be $DFA$ for $Half(L)$ ]


Example: Suppose $L=\{ab,bb\},$ $Half(L)=\{a, b\}$

Step1. Design $DFA, M$ for $L$ enter image description here

Step2. Reversal of $M$ which becomes $NFA,$ $N.$

enter image description here

Step3. $\delta(q_0,b)=q_1$ for $M$ and $\delta(q_2,b)=q_1$ for $N.$

Step4. We see that $q_1$ state is common for both $M$ and $N.$ So new final state is $q_1.$

Step5. New $DFA$ of $Half(L)$ or $FirstHalve(L)$ which accepts only $\{a, b\}$ enter image description here

Miscellaneous Examples try yourself:
  • $L=a^∗$ , then $half(L) =a^∗$
  • $L=a(aa)^∗$, then $half(L) =\phi$
  • $L=a^∗b^∗$, then $half(L) =a^∗b^∗$
$\endgroup$
9
  • $\begingroup$ Awesome! Thank you! In your example, I think you mean $L=\{aa,bb\}$ :) $\endgroup$
    – Math4me
    Jun 17 at 9:32
  • 1
    $\begingroup$ No, I mean $L=\{ab,bb\},$.Corrected. $\endgroup$ Jun 17 at 9:40
  • $\begingroup$ Yes that is it :) $\endgroup$
    – Math4me
    Jun 17 at 10:08
  • $\begingroup$ Unfortunately, the construction will not work as intended. You have found sates where there exists a string before and after of the same lenght. Not necessarily all strings before and after have that property. Consider an automaton for $( a^*b + (aa)^*c)\cdot (aa)^*$ with a state at the position of the dot $\cdot$. The $a^*b$ are first halves, the $(aa)^*c$ are not. $\endgroup$ Jun 17 at 14:31
  • $\begingroup$ @HendrikJan odd length strings don't have any half. Only even length strings have halves. The half of $a^*b$ is $a^+$ , you can easily construct by my algorithm. $\endgroup$ Jun 17 at 14:40
1
$\begingroup$

I guess this question Prove half(L) is regular is the same.

There are several ways to prove a language is regular:

  1. By building DFA, NFA, or Regular Expression (which is the case in your question).
  2. Using the Myhill-Nerode theorem. However, in general, it's used only to prove a language isn't regular.
  3. By contradiction. That is if you assume that the language isn't regular and show that this leads to another known regular language to be 'not regular' then your language is regular.
  4. By using closure properties. That is if you show that its complement, reverse, etc... is regular then the language is regular.

Note: You can't use the pumping lemma to prove a language is regular.

In the end, I don't assume there is a simpler way to prove your language is regular using one of the above options. Since you almost know nothing about that language it's hard to use the above strategies.

$\endgroup$
1
  • $\begingroup$ Thank you for your answer! :) $\endgroup$
    – Math4me
    Jun 17 at 9:32
1
$\begingroup$

The language $\mathrm{half}(L)=\{x\mid xy\in L,|x|=|y|\}$ can be quite complicated, compared to the original language $L$. I am afraid that there is no simple construction and we have to keep track of the behaviour of the automaton both forward and backward, which is the product automaton you are referring to.

Let me walk through an example, take $L = (aaa)^*b(cc)^*$, a rather innocent language, which can be accepted by a five-state automaton.

(aaa)b(cc)

We can manually check that $\varepsilon$, $a$ and $a^4$ are not in $\mathrm{half}(L)$, where as all other strings in $a^*$ are $\mathrm{half}(L)$, as follows: $aa|ab$, $aaa|bcc$, $a^5|a{\cdot}a^3b$, $a^6|a^3bc^2$, $a^7|a^2bc^4$, $a^8|a{\cdot}bc^6$, etcetera. (That is not a proof, I know.) Turn to strings of the form $a^*b$. They can only belong to $\mathrm{half}(L)$ if there exists a "devision" of the form $a^{3k}b|c^{2\ell}$. This means that $3k+1$ should be even, or $k$ is odd. Then we get $a^3b$, $a^9b$, $a^{15}b$, ... in $\mathrm{half}(L)$. I will not repeat this for strings ending in $c$'s, but for $a^{3k}bc^{m}|c^{n}$ we get the same restriction on $k$ (and no restriction on $m$).

Thus $\mathrm{half}(L)= a^*\setminus\{a^0,a^1,a^4\} \cup a^3 (a^6)^*b c^*$.

Now the automaton version, using the forward-backward method.

The product construction starts with two states in the automaton, the initial and final states. It follows the first state as in the original automaton, but for the second we follow an edge (any label) backwards, and we know that from that second state we can reach the final state in exactly the number of steps we have done so far. Accept when both states are equal. The "hard proof" you mention. Here is what I got. Choosing the backward edge is non-deterministic (several edges may point to the state) and the result is quite unclear. Note the large blop of useless states at the top.

nondeterministic half

This can be improved in this case by first determinizing the backward automaton. We keep track of sets of (backward) reachable states. Now accept if the forward state is an element of the backward set. (eg., $0\in S=\{0,1,4\}$.) Lower diagram is the final result of this "deterministic" product construction. Here a line of useless states at the bottom that can be removed without changing the language.

deterministic half

To keep the answer of reasonable size, the figures are reduced. If you click on the image you get again reduced size. Remove the final 'm' from the filename and it will be better readable.

note. In the answer to Is Lhalf={ w :for some z∈L,x∈Σ∗,z=wx∧|w|=|x| } regular? [duplicate] a slightly different construction is given. Rather than forward-backward simulation, the automaton guesses the middle state $q$ and simulates two parallel forward computations, the second one starting in $q$. When the first computation ends in $q$ and the second in a final state, we accept.

$\endgroup$
5
  • $\begingroup$ In your first diagram you made loop of $aa$ it should be $cc$? $\endgroup$ Jun 18 at 18:13
  • $\begingroup$ @user19121278 Indeed! Thanks, corrected. $\endgroup$ Jun 18 at 22:33
  • $\begingroup$ I have made Your language by my algorithm still it's working as good. $\endgroup$ Jun 18 at 22:39
  • $\begingroup$ $Half(L), |x|=|y|$ checking by single tape with one head(classical DFA ) is possible? $\endgroup$ Jun 18 at 22:46
  • $\begingroup$ Thank you so much for this answer! I appreciate that!! :D $\endgroup$
    – Math4me
    Jun 19 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.