Слайд 2Deterministic finite automata
Deterministic finite automaton (DFA) consists of three parts: a tape,
![Deterministic finite automata Deterministic finite automaton (DFA) consists of three parts: a](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1085218/slide-1.jpg)
a tape head (or, simply, head), and a finite control.
Слайд 3Deterministic finite automata
![Deterministic finite automata](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1085218/slide-2.jpg)
Слайд 4Deterministic finite automata
The tape head scans the tape, reads symbols from the
![Deterministic finite automata The tape head scans the tape, reads symbols from](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1085218/slide-3.jpg)
tape, and passes the information to the finite control.
Слайд 5Deterministic finite automata
At each move of the DFA, the head scans one
![Deterministic finite automata At each move of the DFA, the head scans](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1085218/slide-4.jpg)
cell of the tape and reads the symbol in the cell, and then moves to the next cell to the right.
Слайд 6Deterministic finite automata
![Deterministic finite automata](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1085218/slide-5.jpg)
Слайд 7Deterministic finite automata
Then, it determines, from the current state and the symbol
![Deterministic finite automata Then, it determines, from the current state and the](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1085218/slide-6.jpg)
read by the tape, how the state is changed to a new state.
Слайд 8Deterministic finite automata
![Deterministic finite automata](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1085218/slide-7.jpg)
Слайд 9Deterministic finite automata
![Deterministic finite automata](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1085218/slide-8.jpg)
Слайд 11Deterministic finite automata
When the DFA halts, it accepts the input string if
![Deterministic finite automata When the DFA halts, it accepts the input string](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1085218/slide-10.jpg)
it halts in one of the final states.
Otherwise, the input string is rejected.
Слайд 13Deterministic finite automata
The transition diagram of a DFA is an alternative way
![Deterministic finite automata The transition diagram of a DFA is an alternative](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1085218/slide-12.jpg)
to represent the DFA.
Слайд 26Nondeterministic finite automata
![Nondeterministic finite automata](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1085218/slide-25.jpg)
Слайд 27Nondeterministic finite automata
![Nondeterministic finite automata](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1085218/slide-26.jpg)
Слайд 28Nondeterministic finite automata
![Nondeterministic finite automata](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1085218/slide-27.jpg)
Слайд 29Nondeterministic finite automata
![Nondeterministic finite automata](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1085218/slide-28.jpg)
Слайд 30Nondeterministic finite automata
![Nondeterministic finite automata](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1085218/slide-29.jpg)
Слайд 31Nondeterministic finite automata
![Nondeterministic finite automata](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1085218/slide-30.jpg)
Слайд 32Nondeterministic finite automata
NFA’s, like DFA’s, can also be represented by transition
![Nondeterministic finite automata NFA’s, like DFA’s, can also be represented by transition](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1085218/slide-31.jpg)
diagrams.
In the transition diagram, we still use a vertex to represent a state and a labeled edge to represent a move, except that we allow multiple edges from one vertex to other vertices with the same label.
Слайд 33Nondeterministic finite automata
![Nondeterministic finite automata](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1085218/slide-32.jpg)
Слайд 34Nondeterministic finite automata
![Nondeterministic finite automata](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1085218/slide-33.jpg)
Слайд 35Nondeterministic finite automata
![Nondeterministic finite automata](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1085218/slide-34.jpg)
Слайд 36Nondeterministic finite automata
![Nondeterministic finite automata](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1085218/slide-35.jpg)
Слайд 38Nondeterministic finite automata
![Nondeterministic finite automata](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1085218/slide-37.jpg)
Слайд 40Nondeterministic finite automata
Some of these computation paths lead to final states
![Nondeterministic finite automata Some of these computation paths lead to final states and some do not.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1085218/slide-39.jpg)
and some do not.
Слайд 41Nondeterministic finite automata
![Nondeterministic finite automata](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1085218/slide-40.jpg)