Детерминированные конечные автоматы

Детерминированный конечный автомат

Определение:

Детерминированный конечный автомат(ДКА) --- набор из пяти элементов [math]\langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to Q \rangle[/math], где [math]\Sigma[/math] -- алфавит, [math]Q[/math] -- множество состояний автомата, [math]s[/math] -- начальное состояние автомата, [math]T[/math] -- Множество допускающих состояний автомата, [math]\delta[/math] -- функция переходов.

Процесс допуска

Процесс допуска слова автоматом выглядит так:

• Изначально автомат находится в стартовом состоянии
• Ему на вход подается строка
• Далее на каждом шагу автомат берет новый символ строки и совершает соответствующий переход в новое состояние, если для символа не задано никакого перехода из текущего состояния, то слово считается недопущенным (в отличие от недетерминированного конечного автомата, где множество переходов из текущего состояния может быть в том числе пустым)
• Слово считается допущенным, если после того, как прочитаны все его символы, автомат оказался в допускающем состоянии.

Для удобства можно ввести следующие обозначения:

• [math]\langle q, \alpha \rangle \vdash \langle p, \beta \rangle[/math], если
  • [math]\alpha = c\beta[/math]
  • [math]\delta (q, c)=p [/math]

• [math]\langle q, \alpha \rangle \vdash^* \langle p, \beta \rangle[/math], если
  • [math]\langle q, c_1 c_2 c_3 ...c_n\beta \rangle \vdash \langle u_1, c_2 c_3 ...c_n\beta \rangle \vdash \langle u_2, c_3 ...c_n\beta \rangle ...\vdash \langle u_{n-1}, c_n\beta \rangle \vdash \langle p, \beta \rangle[/math]

Лемма:

[math]\langle q, \alpha \rangle \vdash^* \langle p, \varepsilon \rangle, \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \rangle \Rightarrow \langle q, \alpha\beta \rangle \vdash^* \langle r, \varepsilon \rangle[/math]

Доказательство:

[math]\triangleright[/math]

[math]\langle q, \alpha\beta \rangle \vdash^* \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \rangle.[/math]

[math]\triangleleft[/math]

Автоматные языки

Определение:

[math]L(\mathcal{A})=\{\alpha| \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle t \in T\}[/math] --- язык автомата [math]\mathcal{A}[/math].