After observing your DFA construction skills, a group called the SuperSecretDFA

Question

After observing your DFA construction skills, a group called the SuperSecretDFA organization has hired you. This group markets on its website that “Our single DFA is the smallest and most efficient of any language over {0, 1} you can give to us.” Now this group, trying to protect their brand and their construction process, tells you that they cannot share with you their DFA, nor its transition function, or anything else about their DFA except the number of states it has: n. You cannot assume anything about their DFA other than the number of states (and of course the alphabet).

(a) (2 points) Exhibit a language L that their super secret DFA cannot recognize only knowing the number of states (n) it has, and prove why L cannot be recognized by their DFA.

(b) (3 points) Show that there are only finitely many possible languages that can be recognized by their DFA by giving an upper bound on how large this finite number can be.

Explanation / Answer

(a) L = {anbn | (a, b) belongs to the input alphabet, n>=1} be a Language that the super secret DFA cannot recognize given the number of states and say the input alphabets. This is because for Language L, there is no finite state machine that will 'count' identical sequences of 'a' and 'b' symbols. In a nutshell, FSMs cannot 'count' as DFA lacks memory component. So, because of shortage of memory DFA cannot store the count of number of a's and later compare with the count of no. of b's. So L cannot be recognized by their DFA.

b) So, we know the Cleene Closure (*) of any RL is also Regular. So if we say we have Set(Regular-Language) = {R1, R2, R3, R4, R5,.....}. The Cleene Closure of Set(Regular-Language) ie Set(Regular-Language) * is also Regular but the upper bound is when we put N (some variable >=1 say) then in that case memory will be required to store the count, whereas in case of Kleene Closure we repeat the string pattern multiple times but without a count of the number of times that we are gonna repeat. This makes the Language decide as to whether its Regular or Non-Regular Language.

Please let me know in case of any clarifications required. Thanks!

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.