Consider an alphabet with a single symbol: = {a}. (a) How many different DFAs with...

Transcribed Image Text:

Consider an alphabet with a single symbol: Σ = {a}. (a) How many different DFAs with exactly 3 states can be constructed? (In other words, how many different 5-tuple formal representations are possible. Note that you can have DFAs that contain states that are unreachable or that have other inefficient behavior. Multiple DFAs may recognize the same language. Count them all.) Assume that the states are qo, 91 and 92. Also assume that go is always the start state. And assume the single symbol alphabet mentioned above. You do not have to draw any state diagrams. Just give a numerical answer. (b) Suppose you are additionally told that q₁ is an accepting state, and 90 and 92 are not accepting states. Now how many different DFAs can be constructed? (c) How many different languages are recognized by the collection of DFAs from part (b)? For each such language, draw a state diagram for a 3-state DFA that recognizes the language (even if it is possible to recognize the language with a smaller DFA) and describe the language using set notation. Consider an alphabet with a single symbol: Σ = {a}. (a) How many different DFAs with exactly 3 states can be constructed? (In other words, how many different 5-tuple formal representations are possible. Note that you can have DFAs that contain states that are unreachable or that have other inefficient behavior. Multiple DFAs may recognize the same language. Count them all.) Assume that the states are qo, 91 and 92. Also assume that go is always the start state. And assume the single symbol alphabet mentioned above. You do not have to draw any state diagrams. Just give a numerical answer. (b) Suppose you are additionally told that q₁ is an accepting state, and 90 and 92 are not accepting states. Now how many different DFAs can be constructed? (c) How many different languages are recognized by the collection of DFAs from part (b)? For each such language, draw a state diagram for a 3-state DFA that recognizes the language (even if it is possible to recognize the language with a smaller DFA) and describe the language using set notation.