- #1
s3a
- 818
- 8
Hello to everyone that's reading this. :)
1. Homework Statement
(Theory of Computation) proof problem about proving that L = L(A) by proving that L ⊆ L(A) and that L(A) ⊆ L:
https://www.docdroid.net/du7lLvh/theproblemanditssolution.pdf
• Mutual simple induction
• Formal usage of transition function of DFAs (meaning knowing how to use the delta notation)
• Potentially, proof by contrapositive
• Knowing that A = B can be proven by proving A ⊆ B and B ⊆ A.
My question is: does the "δ̂(p, w) = p ⇒ w has even number of 1's" from second part (L ⊆ L(A)) need the first part (L(A) ⊆ L) to already be shown, or is it completely independent, such that the second part (L ⊆ L(A)) could have been cut and pasted, verbatim, before the first part (L(A) ⊆ L)?
Any input would be GREATLY appreciated!
1. Homework Statement
(Theory of Computation) proof problem about proving that L = L(A) by proving that L ⊆ L(A) and that L(A) ⊆ L:
https://www.docdroid.net/du7lLvh/theproblemanditssolution.pdf
Homework Equations
• Mutual simple induction
• Formal usage of transition function of DFAs (meaning knowing how to use the delta notation)
• Potentially, proof by contrapositive
• Knowing that A = B can be proven by proving A ⊆ B and B ⊆ A.
The Attempt at a Solution
My question is: does the "δ̂(p, w) = p ⇒ w has even number of 1's" from second part (L ⊆ L(A)) need the first part (L(A) ⊆ L) to already be shown, or is it completely independent, such that the second part (L ⊆ L(A)) could have been cut and pasted, verbatim, before the first part (L(A) ⊆ L)?
Any input would be GREATLY appreciated!