Closed regular languages

78 Views Asked by At

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$ $\}$

2

There are 2 best solutions below

0
On BEST ANSWER

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.

0
On

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