1
$\begingroup$

Suppose that $L$ is a regular language and $0<\alpha<1$ and $\alpha \in Q$. Define $L_\alpha$ as

$$L_\alpha = \{\omega \in \Sigma^* \mid \exists \omega_1 \in \Sigma^* .\omega\omega_1 \in L,\frac{|\omega|}{|\omega\omega_1|}=\alpha\}$$

How do I prove that $L_\alpha$ is regular?

Here is my attempt. If we assume that $D$ is the automaton that recognize $L$ with $Q=\{q_0,...,q_n\}$, if $\delta(q_0,\omega\omega_1)\in F$ and $\delta(q_0,\omega)=q_i$ we can define $D_1$ such that $\delta_1(q_0,\omega)=r_{i-1}$ (for $r_i \in F_1)$, but the problem is I can't define $\delta_1(q_0,a) $for $a\in \Sigma$.

$\endgroup$
1
$\begingroup$

Try proving it for $\alpha = 1/2$ first. Construct a non-deterministic automaton that recognizes $L_\alpha$. Before you start reading in the string $w$, guess something about where you will be in the future. What would you like to guess? What would help you?

$\endgroup$
  • $\begingroup$ Thank you,for other value of $\alpha$(assume that $\omega_1 > \omega$ and their difference is $n$,then we should add n states at the beginning of $D$,am I right? $\endgroup$ – MAh2014 Sep 21 '17 at 20:44
  • $\begingroup$ @MAh2014, it's your exercise, so I'll let you figure that out. The way to decide if it works is to prove your answer correct. If you're having a hard time with that, try $\alpha = 1/3$ and $\alpha = 2/3$ next. $\endgroup$ – D.W. Sep 21 '17 at 21:12

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.