$A=(X,S,F,S_0,δ)$, где:
- $X=\{...\}$ - конечное множество входящих символов (входящий алфавит)
- $S=\{...\}$ - конечное непустое множество состояний
- $F⊂S$ - множество выделенных заключительных состояний
- $S_0$ - начальное состояние
- $δ$ - набор команд $X \times S→S$, $(S_i;x)→S_j$
  
Автомат, находясь в состоянии $S_i$, получает на вход $x$ и переходит в состояние $S_j$.  
*Замечание:* Функция $δ$ может быть частичной, то есть она может быть определена для некоторых значений ее $D$.  
Конечные автоматы могут быть:
- **Детерминированные (ДКА)** - существует единственная команда $(S_i;x)$ с переходом в состояние $S_j$
	![Детерминированный конечный автомат](../Pictures/03_01.%20Детерминированный%20конечный%20автомат.png)
- **Недетерминированные (НКА)** - команда $(S_i;x)$ может быть с переходом в несколько состояний: $(S_i,x)=S_j$, $(S_i,x)=S_k$
	![Недетерминированный конечный автомат](../Pictures/03_02.%20Недетерминированный%20конечный%20автомат.png)
  
Автомат **допускает слово** в заданном алфавите $X$, если, начав работу с заданным словом, он останавливается в одном из выделенных заключительных состояний.  
**Работа автомата над заданным словом** - это путь из начальной вершины $S_0$. Последовательность вершин этого пути - это последовательность состояний, принимаемых автоматом, а образ пути по дугам - это читаемое слово. Любой путь в графе автомата, начинающийся в вершине $S_0$ и заканчивающийся в вершине $F⊂S$ порождает слово, допускаемое состояние.  
Конечный автомат часто используется для задания множества допустимых входных последовательностей - **слов**.  
Конечный автомат может быть:
- распознавателем
- преобразователем
  
Конечный автомат является **распознавателем**, если он при работе с заданным словом, начав с состояния $S_0$, останавливается в одном из заключительных состояний этого автомата $F$.  
**Пример 1:**  
$A=(X,S,F,S_0,δ)$  
$X=\{a,b,c\}$  
$S=\{0,1,2,3,4,5\}$  
$F=\{3,5\}$  
$S_0=\{0\}$  
$δ:$  
$(S_0,a)→S_1$  
$(S_1,b)→S_2$  
$(S_2,c)→S_3$  
$(S_0,c)→S_4$  
$(S_3,c)→S_5$  
![Граф конечного автомата из примера 1](../Pictures/03_03.%20Граф%20конечного%20автомата%20из%20примера%201.png)  
**Пример 2:**  
$A=(X,S,F,S_0,δ)$  
$X=\{a,b\}$  
$S=\{0,1,2,3\}$  
$F=\{1,2\}$  
$S_0=\{0\}$  
$δ:$  
| $(S_0,a)→S_1$ | $(S_1,a)→S_3$ | $(S_1,c)→S_2$ | $(S_2,b)→S_0$ |
| ------------- | ------------- | ------------- | ------------- |
| $(S_0,b)→S_1$ | $(S_3,b)→S_3$ | $(S_2,c)→S_1$ | $(S_3,a)→S_0$ |
| $(S_0,c)→S_0$ | $(S_1,b)→S_2$ | $(S_2,a)→S_0$ | $(S_3,c)→S_0$ |
  
![Граф конечного автомата из примера 2](../Pictures/03_04.%20Граф%20конечного%20автомата%20из%20примера%202.png)  
Проверка слов:  
1) $aaba - S_0$ - не подходит
2) $abcc - S_2$ - подходит
3) $bcccc - S_1$ - подходит
4) $aabbcc - S_0$ - не подходит
5) $bacc - S_0$ - не подходит
  
**Пример 3.** Построить конечный автомат, распознающий множество констант  
1) Целые константы: 35, -35, +356
  
$A=(X,S,F,S_0,δ)$  
$X=\{0..9 (ц), +, -\}$  
$S=\{0,1,2\}$  
$F=\{2\}$  
$S_0=\{0\}$  
$δ:$  
$(S_0,+)→S_1$  
$(S_0,-)→S_1$  
$(S_0,ц)→S_2$  
$(S_1,ц)→S_2$  
$(S_2,ц)→S_2$  
![Граф конечного автомата из примера 3.1](../Pictures/03_05.%20Граф%20конечного%20автомата%20из%20примера%203.1.png)  
2) Вещественные константы: 35.14, +1.412, -356.12, .768
  
$A=(X,S,F,S_0,δ)$  
$X=\{0..9 (ц), +, -, .\}$  
$S=\{0,1,2,3,4\}$  
$F=\{2,4\}$  
$S_0=\{0\}$  
$δ:$  
$(S_0,+)→S_1$  
$(S_0,-)→S_1$  
$(S_0,ц)→S_2$  
$(S_1,ц)→S_2$  
$(S_2,ц)→S_2$  
$(S_0,.)→S_4$  
$(S_1,.)→S_3$  
$(S_3,ц)→S_2$  
$(S_2,.)→S_4$  
$(S_3,.)→S_4$  
$(S_4,ц)→S_4$  
![Граф конечного автомата из примера 3.2](../Pictures/03_06.%20Граф%20конечного%20автомата%20из%20примера%203.2.png)  
Распознавание констант:  
$35.14: 0→2→2→4→4→4$  
$-356.12: 0→1→2→2→2→4→4→4$  
$.768: 0→4→4→4→4$  
$+1.412: 0→1→3→4→4→4→4$  
3. Вещественные константы с плавающей точкой: 3.14E+00, 0.314E+01, 31.4E-01, 314.0E-02
  
![Граф конечного автомата из примера 3.3](../Pictures/03_07.%20Граф%20конечного%20автомата%20из%20примера%203.3.png)