2
$\begingroup$

I'm not sure if my logic is correct when it comes to the algorithm for decision problems. The concept is confusing me when I fail to distinguish its answer from that of a proof.

For example:

Given two finite automata $M_1, M_2$ that operate on a common alphabet, find an algorithm to show that:

$$L(M_1) \subseteq L(M_2)$$

And how I viewed it was:

  1. Find a string $w$ from the alphabet $\Sigma$
  2. Feed $w$ to $M_2$; if accepted then $w$ is part of $L(M_2)$
  3. Feed $w$ to $M_1$; if accepted then $w$ is part of $L(M_1)$
  4. If $w$ was accepted by $M_2$ and $M_1$, then $L(M_1) \subseteq L(M_2)$
  5. Otherwise reject

Unlike proofs which require mathematical arguments, algorithms for decision problems seem more like a logical flow or sequence description. If it were a proof I would have to perhaps design a language or expression using properties and lemmas where as here I just describe the process of determining if the statement can be answered (via "yes" or "no").

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ An algorithm doesn't "show" something - it determines whether a certain property holds or not. $\endgroup$ – Yuval Filmus Feb 22 '18 at 14:20
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Feb 22 '18 at 16:04
  • $\begingroup$ Hint: Try to express the criterion at hand in a way so that you can re-use algorithms you already know (or are easier to come up with). $\endgroup$ – Raphael Feb 22 '18 at 16:08
3
$\begingroup$

Your algorithm is not really specified completely, since you don't explain how you choose the word $w$. However, even once you do specify how $w$ is chosen, your algorithm will be incorrect. The reason is that it is completely symmetric in $M_1$ and $M_2$. In other words, if the algorithm accepts on the pair $(M_1,M_2)$, then it will also accept on the pair $(M_2,M_1)$. This means that it will necessarily fail for machines satisfying $L(M_1) \subseteq L(M_2)$ but $L(M_2) \nsubseteq L(M_1)$.

Presumably in class you were shown other decision algorithms for regular languages. I suggest you try to emulate them. As an example, here is an algorithm that determines whether $L(M) \neq \emptyset$, for a DFA $M$.

Input: A DFA $M = \langle \Sigma, Q, q_0, F, \delta \rangle$.

Accept if some state in $F$ is reachable from $q_0$, and reject otherwise.

(In class you will probably need to be more verbose.)

To show that this algorithm is valid, we need to show two things:

  1. If $L(M) \neq \emptyset$, then the algorithm accepts.
  2. If $L(M) = \emptyset$, then the algorithm rejects.

To prove the first part, suppose that $w \in L(M)$. By definition, the state $\delta(q_0,w) \in F$ is reachable from $q_0$, so the algorithm accepts.

To prove the second part, we will prove the contrapositive: if the algorithm accepts, then $L(M) \neq \emptyset$. Suppose that some state $q \in F$ is reachable from $q_0$. This means that there is some path from $q_0$ to $q$. If $w$ is the concatenation of all symbols on this path, then $\delta(q_0,w) = q \in F$, and so $w \in L(M)$, showing that $L(M)$ is non-empty.

(Once again, in class you will probably need to be more verbose.)

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Sound enough example, would you mind expanding on the problem I have though? Exercise has since passed, so I want to review and learn from what I've done wrong. Your statement regarding symmetry makes perfect sense, though I am still unsure how to determine that a language is a subset of another. $\endgroup$ – pstatix Feb 22 '18 at 14:39
  • 1
    $\begingroup$ I think it's better if you solved this exercise on your own. $\endgroup$ – Yuval Filmus Feb 22 '18 at 14:45
  • $\begingroup$ I've already given my attempt, I'm seeking guidance on how to correct the error. Even if you give me a "process flow", if I have missed something entirely, your flow will be useless unless my error is pointed out and a correction given. $\endgroup$ – pstatix Feb 22 '18 at 14:47
  • 1
    $\begingroup$ Your algorithm is too far off the mark for there to be any error which can be pointed out. The real problem is that you are unable to spot that your attempt is way off. I suggest studying again that part of your course which discusses decision problems. $\endgroup$ – Yuval Filmus Feb 22 '18 at 14:51
  • $\begingroup$ If one is able to establish a metric that qualifies "way off", then one is able to determine relative error...otherwise, what is "way off"? How much is "way off"? From where am I "way off"? Cannot contradict yourself at the same time... $\endgroup$ – pstatix Feb 22 '18 at 14:54
1
$\begingroup$

This algorithm isn't correct. There could be some $w \in \Sigma ^* : w \in L(M_1) \wedge w \in L(M_2) $ although $L(M_1) \nsubseteq L(M_2)$ Assuming in your first step the algorithm finds such a $w$, the algorithm would output the wrong answer.

To my mind your exercise is formulated in a very strange way, but i think you should find an algorithm $A$ with $\forall finite automata M_1,M_2: A(<M_1,M_2>) = 1 \Leftrightarrow L(M_1) \subseteq L(M_2)$

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ There is nothing strange about the exercise. On the contrary, it is a standard exercise. $\endgroup$ – Yuval Filmus Feb 22 '18 at 14:47

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.