2.1.1. (finite automaton, finite-state machine) - 
, 
- ( ) , 
- ,
, 
. Q (state), I - (initial) , F - (final, accepting) . 
, 
(transition) p q, x - (label) .
2.1.2. Q = {1,2}, 
, I = {1}, F = {2},
- .
2.1.3. (state diagram) ( (transition diagram)). , - . p q, x, , . . .
2.1.4. 2.1.2.
2.1.5. , . . .
2.1.6. 2.1.2.
2.1.7. (path) - 
, 
i. q0 - qn - n - w1...wn - .
2.1.8. 
. - 
, .
2.1.9. I, F.
2.1.10. 2.1.2. 
. - baaab. - 4.
2.1.11. w (is accepted, is recognized) M, .
2.1.12. , M, - L(M), ( ). , M (recognizes, accepts) L(M).
2.1.13. 
, , , .
2.1.14. , Q = {1,2}, , I = {1}, F = {1,2},
2.1.15. , .
2.1.16. L (finite-state language), , .
2.1.17. , (. 2.3.3.).
2.1.18. 
. 
.
|
|
|
2.1.19. .
2.1.20. q (reachable) p, , p, - q.
2.1.21. , .
2.1.22. , Q = {1,2,3,4}, 
, I = {1,2,4}, F = {1,3,4},
( ), 2.1.21. 
, Q' = {1,4}, I' = {1,4}, F' = {1,4},
2.1.23 (finite-state transducer), "" . ( ).
.
2.1.24. , 
2.1.25. , 
2.1.26. , 
2.1.27. , 
2.1.28. , 
2.1.28. , 
, 
, 
