patternMinor
Comparing DFA's produced languages
Viewed 0 times
produceddfacomparinglanguages
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#18214, answer score: 4
Revisions (0)
No revisions yet.