8
$\begingroup$

Given some regular language $L$, show that $L$ is closed under the following operations:

$$\begin{align*} \min(L) &= \{w\mid w\in L,\text{ but no prefix of }w\text{ is in }L \}\\ \max(L) &= \{w\mid w\in L,\text{ but for no }x\text{ other than }\epsilon\text{ is }wx\in L \} \end{align*}$$

It seems that $\min(L)=\max(L)$, is this true? If not, what is the simplest way to show that both $\min(L)$ and $\max(L)$ are regular? I have seen solutions involving homomorphisms, but am hoping that there is a simpler way to approach these problems.

$\endgroup$

1 Answer 1

9
$\begingroup$

Let $L=\{a^n:n\ge 2\}$; then $\min(L)=\{aa\}$, and $\max(L)=\varnothing$, so $\min(L)\ne\max(L)$.

One fairly easy way to prove that $\min(L)$ or $\max(L)$ is regular is to start with a DFA that recognizes $L$ and modify it to accept $\min(L)$ or $\max(L)$. Let $M=\langle Q,\Sigma,\delta,q_0,A\rangle$ be a DFA that accepts $L$; $Q$ is the set of states, $\Sigma$ is the input alphabet, $\delta$ is the transition function, $q_0$ is the initial state, and $A$ is the set of acceptor states. (You may know them as final states.) I’ll sketch the modifications and leave the detailed verification to you.

  • To get a DFA that accepts $\min(L)$, add a new trap state $q^*$ and modify $\delta$ so that any input to an acceptor state sends $M$ to $q^*$.

  • To get a DFA that accepts $\max(L)$, you need only change some acceptor states to non-acceptor states. Specifically, say that a state $q\in Q$ is non-terminal if there is some non-empty word $w$ that sends $M$ from $q$ to an acceptor state, and let $N$ be the set of non-terminal states of $M$. If $A'=A\setminus N$, the automaton $\langle Q,\Sigma,\delta,q_0,A'\rangle$ recognizes $\max(L)$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .