2
$\begingroup$

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

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

2 Answers 2

3
$\begingroup$

Your example is perfect.

Being simple is an advantage and not a problem ;)

$\endgroup$
2
$\begingroup$

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) $$

$\endgroup$

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.