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$.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
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?

Improve this answer
$\endgroup$
2
  • $\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, 2017 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, 2017 at 21:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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