11
$\begingroup$

I've see couple of approaches to this kind of questions yet I have no clue how to approach this one.

Let L be regular language, and let $half(L)$ be: $half(L) = \{u \mid uv \in L\ s.t. |u|=|v|\}$. Prove that if $L$ is regular then $half(L)$ is regular too.

I tried to make a new regular language, $Even(L)$ that recognizes all the even words in $L$ (due to the fact that if we want to slice in half the total length must be even) and from there to "capture" the half words. But I still think it isn't quite correct.

Would like to understand the logic behind a proper solution rather than just the solution :)

Thanks!

$\endgroup$
9
  • $\begingroup$ infolab.stanford.edu/~ullman/ialcsols/sol4.html, exercise 4.2.8 $\endgroup$ Nov 21, 2015 at 13:49
  • $\begingroup$ @HennoBrandsma do you mind further elaborating about the solution? I didn't get the part about the accepting states and that they should be reached by epsilon-moves from any point $\endgroup$
    – Aviad
    Nov 21, 2015 at 13:55
  • $\begingroup$ Basically you construct an automaton for half $L$ from one for $L$. $\endgroup$ Nov 21, 2015 at 13:56
  • $\begingroup$ This part I've got, I just didn't get the logic behind switching between the duplicates $\endgroup$
    – Aviad
    Nov 21, 2015 at 13:59
  • $\begingroup$ Are you allowed to use NFA's as well? $\endgroup$ Nov 21, 2015 at 14:14

1 Answer 1

15
$\begingroup$

Let $A = (\delta_A, Q, q_0, F)$ be a DFA for $L$ (in some alphabet $\Sigma$).

Then define $B$ as follows:

  • The states $Q_B$ of $B$ are of the form $[q,S]$ where $q \in Q$ and $S \subseteq Q$.
  • The initial state of $B$ is $[q_0, F]$.
  • $\delta_B([q,S],a) = [\delta_A(q,a), T]$ where $T = \{p \in Q: \exists b \in \Sigma: \exists p' \in S: \delta_A(p,b) = p' \}$
  • The accepting states of $B$ are $F_B = \{[q,S] : q \in S \}$.

Then we have the following invariant by construction: all reachable states $[q,S]$ after some input are such that $q$ is the state that $A$ would be in after reading that input, and the states in $S$ are all those states such that there is a path from that state to an accepting state (in $A$) that has the same length as the input that was read.

This holds for the initial state (no input, so the only state $A$ could be in is $q_0$ and the only accepting states on no input are those in $F$).

The way the transition rule is defined also upholds the relation: the first part just does what $A$ would have done on that extra letter, and we update the states so that there is a path to an accepting state that is 1 step longer. We could formally prove it by induction on the length of the input.

And when we are in a state $[q,S]$ with $q \in S$ after reading some input $w_1$, we know that $q$ is the state of $A$ after reading $w_1$ and as $q \in S$ there is some input $w_2$ with $|w_1| = |w_2|$ that induces a path from $q$ to an accepting state, which means that $w_1w_2 \in L$, and so $w_1 \in \operatorname{half}(L)$.

(source: this solution, a bit reformulated)

$\endgroup$
5
  • $\begingroup$ Thanks :) Still working on fully understading this. on the delta, you've used 'small' s (rather than big), you indicate by that that s belongs to S ? or the string we've read so far? $\endgroup$
    – Aviad
    Nov 21, 2015 at 15:07
  • 1
    $\begingroup$ I corrected that typo $\endgroup$ Nov 21, 2015 at 16:12
  • $\begingroup$ Thanks! Another one to fix is the brackets in the initial state of B (wrote () rather than [] ) $\endgroup$
    – Aviad
    Nov 22, 2015 at 0:33
  • 6
    $\begingroup$ I think this solution 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. $\endgroup$
    – Arka
    Aug 30, 2018 at 8:07
  • $\begingroup$ Very well explained! @ArkaGhosh $\endgroup$
    – rohith
    Sep 24, 2019 at 8:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .