Are regular languages closed under the following construction?

$f(L) = \{w \mid w \in L$ and for all prefixes $x$ of $w$ it holds that $x \notin L$ $\}$

  • $\begingroup$ @Magdiragdag both formalisms are equivalent i think $\endgroup$ – collapsar Apr 3 '14 at 12:00
  • $\begingroup$ @Magdiragdag i think it was. the implication excluding certain elements in $L$ only applies if $|w| > 1$, so $\epsilon \in L$ is neither eliminated nor introduced by $f$. $\endgroup$ – collapsar Apr 3 '14 at 12:11
  • $\begingroup$ @Magdiragdag ok, so you regard $\epsilon$ as a prefix of any $w \ in L, |w| > 1$. i interpreted the op's phrasing meaning as 'non-empty prefix'. $\endgroup$ – collapsar Apr 3 '14 at 12:17

Yes, $f(L)$ is regular if $L$ is.

Hint. Take a deterministic finite automaton whose language is $L$ and remove all the outgoing transitions from the accepting states.


If $A$ is the alphabet, then $f(L) = L - LA^+$.


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.