3
$\begingroup$

I'm working on some questions to bone up on my knowledge of DFA's for a computing class and I've run across the following problem that is giving me some issues. If we have some DFA M = (Q, Σ, δ, q0, F) and some other DFA M' = (Q, Σ, δ, q0, F') where F is a proper subset of F', are the following relations possible or not between the two produced languages?

1) L(M) ⊂ L(M')

2) L(M) ⊃ L(M')

My current theory is that the first one is not possible, due to the fact that the first machine has fewer finish states than the other, thus the language must be larger and cannot be subset to M'. This would of course mean that the second relationship is possible, since M must contain M'. Am I on the right track here and if so, how could I prove this?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Are you sure that the first machine has more final states than the other? You write "where F is a proper subset of F'. $\endgroup$ – Mike B. Nov 21 '13 at 7:39
  • $\begingroup$ Ah yes, my mistake. In that case, I would think statement one would be possible and statement two is not possible. Is this the right line of thought here? $\endgroup$ – user11521 Nov 21 '13 at 13:23
  • 2
    $\begingroup$ Yes, that is the right line of thought. In order to prove this, you can do this in 2 steps: First prove that one language is contained in the other. You can prove this by showing that if any word $w$ is accepted by M, then it must be accepted by M' as well. Second you must prove that there is a word $w'$ that is in the language of M', but not in the language of M. In both cases you should exploit that $F \subset F'$. (For the second part the $\subsetneq$ becomes important). $\endgroup$ – Mike B. Nov 21 '13 at 14:55
  • 2
    $\begingroup$ @Mike B. Turn into an answer? $\endgroup$ – Yuval Filmus Nov 27 '13 at 9:15
4
$\begingroup$

L(M) ⊂ L(M') can be proved as below:

Suppose a string 'w' ∈ L(M') .
Since it is given that F is a proper subset of F' , there exists a state q1 such that
q1 ∈ F' but not to F.

Since the transition function is same for both the DFAs, hence there is a transition possible as below:
δ(q0, w) = q1
which means the state change takes place from the initial state to the state q1 on reading the input symbols from the string 'w'.

Since q1 ∈ F' but not to F, we can say that 'w' does not belong to L(M).

On the same lines it can also be proved that any string in L(M) is also present in L(M'), thereby proving the relation.

|cite|improve this answer
$\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.