東京大学 情報理工学系研究科 コンピュータ科学専攻 2015年2月実施 問題2
Author
kainoj, 祭音Myyura
Description
Let us consider nondeterministic finite automata (NFA) and deterministic finite automata (DFA) over the alphabet

recognizes the language
Here
Answer the following questions.
(1) Present an NFA, with at most four states, that recognizes the language
Here
(2) Present a DFA that recognizes the language
(3) A DFA that recognizes the language
(4) Argue for the following statement:
- To recognize the same language, a DFA possibly needs the number of states that is exponentially bigger than an NFA does.
Kai
(1)

(2)

(3) + (4)
I'll prove that DFA that recognizes
has no less than
Intuitively we need
Suppose that there's DFA
- if
, then and . Which means that state is both accepting and non-accepting. - if
, then we can append 's to both and . Then a state in which is after reading and is both accepting and non-accepting.
In both cases we get lead to contradiction.
Thus, DFA recognizing
- (3): Let
. Then DFA recognizing has no less than states. - (4): NFA recognizing
has exactly states. Equivalent DFA has states.