9
$\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
  • $\begingroup$ This is exercise 4.2.6 a), b) of Hopcroft, Motwani, Ullman's Introduction to Automata Theory, Languages, and Computation 3rd Ed. $\endgroup$ Commented 15 hours ago

1 Answer 1

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.