"In mathematics, the pigeonhole principle states that if n items are put into m pigeonholes with n > m, then at least one pigeonhole must contain more than one item. " - Wikipedia
i was through that this is an obvious question, why we need a principle for that.
but after i finish Assignment question 1, i realize that it is useful method.
Assume there is a DFSA(D1) for L with fewer than 16 states. #so there is at least 2 unique |string| = 4, go through the DFSA(D1) to the same state by Pigeonhole Principle.
Two string start with the same states but end up with different that cause the contradiction.
No comments:
Post a Comment