Math Is Fun Forum
You are not logged in.
- Topics: Active | Unanswered
Pages: 1
#1 Help Me ! » Designing an NFA that accepts binary strings divisible by 5 or 6 » 2014-09-07 10:57:10
- Lolligirl
- Replies: 0
Hello everyone! I'm trying to make a transition diagram for an NFA that accepts strings that are either divisible by 5 or by 6. Here's the specific question:
Question: Present a transition diagram for an NFA that recognizes the set of binary strings that starts with a 1 and, when interpreted as entering the NFA most to least significant digit, each represents a binary number that is divisible by either five or six. Thus, 101, 110, 1100, 1111 are in the language, but 111, 1011 and 11010 are not.
Here is my divisible by 5 NFA:
But how do I make a transition diagram that does divisible by 6, and then combine it with this one?
Any help at all is greatly appreciated! 
#2 Re: Help Me ! » Finish this mathematical induction problem » 2014-08-28 03:15:34
Is it that complex? Wow! 
There was a similar problem to this done, except with taking the Cartesian product three times instead of four, and it seemed not crazt complex:
Question: Prove if S is any finite set with |S| = n, then |SxSxSxS| ≤ |P(S)|, for all n ≥ N, where N is some constant, the minimum value of which you must discover and use as the basis for your proof.
Proof: (This is the same as showing n^4 <= 2^n, for all n ≥ N. We shall show this is true when N=16.)
Basis: 16^4 = (2^4)^4 = 2^16 ≤ 2^16. This proves the base case.
I.H.: Assume for some K, K ≥ 16, K^4 ≤ 2^K.
I.S. (K+1): (K+1)^4 = K^4 + 4K^3 + 6K^2 + 4K + 1
≤ K^4 + 4K^3 + 6K^3 + 4K^3 + K^3 since K ≥ 1
= K^4 + 15K^3 ≤ K^4 + K^4 since K ≥ 16
≤ 2^K + 2^K by IH
= 2^(K+1)
Thus, (K+1)^4 <= 2^(K+1) and the I.S. is proven.
I have been trying to extend this to adding one more Cartesian product, but wasn't sure exactly how the line
"(K+1)^4 = K^4 + 4K^3 + 6K^2 + 4K + 1"
became
"≤ K^4 + 4K^3 + 6K^3 + 4K^3 + K^3 since K ≥ 1"!
#3 Help Me ! » Finish this mathematical induction problem » 2014-08-27 13:44:30
- Lolligirl
- Replies: 2
Hello everyone! I started on this mathematical induction problem and I am not sure how to finish it past a certain point. Here it is:
Question: Prove that if S is any finite set with |S| = n, then |S x S x S x S x S| ≤ |P(S)|,for all n ≥ N where N is some constant, the minimum value of which you must discover and use as the basis for your proof.
Because the Cartesian product grows at the rate of 2^n, we must show that n^5≤ 2^n for n ≥ N, and find what N is.
Base Case: n = 23.
23^5 ≤ 2^23 = 6436343 ≤ 8388608. Base case proven. (This is not true for any n less than 23 since 22^5 = 5153632 and 2^22 = 4194304, and 5153632 is not less than 4194304.)
Inductive Hypothesis: Assume for some k ≥ 23 that k^5 ≤ 2^k.
Inductive Step: (k+1)^5 ≤ 2^(k+1)
(k+1)^5= k^5 + 5k^4 + 10k^3 + 10k^2 + 5k + 1
...
I am not sure where to go from here, to be honest. Would anyone care to help? It would be much appreciated!
Pages: 1