1
$\begingroup$

Prove that if $ L \subseteq \Sigma^\star$ is regular, $L'$ is also regular where

$$ L' = \{w\mid{uw \in L \mbox{ for some string }u \in \Sigma^\star}\}$$

I'm new learning formal language and haven't proved stuff like this. But I'm sharing my thoughts here to make sure I'm on the right track. The first idea came to my mind is using close properties. Since $u$$w$ $\in$ L and $u$ $\in$ $\Sigma^\star$ so we know L is also regular. $L'$ is the concatenation of two regular languages. The regular languages are closed under concatenation thus $L'$ is also regular.

Any feedback or suggestions?

$\endgroup$
0
$\begingroup$

Given a DFA for $L$, let $\mathcal{Q}$ be the set of states that are reachable from the start state. Construct an NFA-$\epsilon$ by adding a new start state $S$ and adding an $\epsilon$-transition from $S$ to each state in $\mathcal{Q}$. You can see the new NFA-$\epsilon$ recognizes $L'$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Your conclusion that $L’$ is a concatenation of two regular languages is wrong.

$L’$ is basically the set of suffixes of all the strings in $L$. Try to prove it for the prefixes and use the “closed under reverse operation” property of regular languages.

Hint for prefix language: make some special states as final state in the DFA of a regular language.

| cite | improve this answer | |
$\endgroup$

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.