# Give an example of a language $L$ where $\min(\max L)\neq \max(\min L)$

Give an example of a language $$L$$ where $$\min(\max L)\neq \max(\min L)$$.

I thought of the following language $$L=\{a,bc, abc\}$$.

$$\min L=\{a,bc\}, \max L = \{abc\}$$ Then: $$\min(\max L)=\min (\{abc\})=\{abc\}\neq \max(\min L)=\max(\{a,bc\})=\{a,bc\}$$ This seems too simple so I'm wondering if it's correct.

The definitions of $$\max, \min$$: $$\min L= \{x|x\in L \land \text{there doesn't exist a non-empty substring }y \text{ of } x \text{ such that } y\in L \}\\ \max L = \{x|x\in L \land \lnot \exists y: xy\in L, y\neq \epsilon\}$$

• min and max of a language are not standard operations. You should provide their definitions. Jan 28, 2019 at 12:33

Now with the definitions it is clear that your example is right. However, your reasoning is not correct. $$bc$$ can be extended to the left by $$a$$ to form a longer string in the language, but there is no extension to the right. The definition of $$max$$ only asks for extensions to the right. Therefore $$bc$$ is also in the $$max$$, and your example works like this:
$$\min(\max L)=\min (\{bc, abc\})=\{bc\}\ \ \neq\ \ \{a,bc\}=\max(\{a,bc\})=\max(\min L)$$