Конечный автомат

В А-грамматике все порождающие правила имеют вид:

A → aB или A → a,

где A,B – нетерминальные символы, а – терминальный символ.

В процессе порождения, начинающегося с начального нетерминала, цепочка всегда имеет очень простой вид: γA, где γ – терминальная цепочка, A – нетерминал. И только на самом последнем шаге этот единственный нетерминал заменяется терминальным символом. Процесс грамматического разбора должен повторять процесс порождения, его можно реализовать с помощью алгоритма, называемого конечным автоматом (КА).

Конечный автомат задается пятеркой множеств:

{Σ, Q, q₀, F, δ},

где Σ – множество (алфавит) входных символов; Q – множество состояний КА; q₀ – начальное состояние, ; F – множество заключительных состояний, ; δ – множество правил перехода, каждое правило имеет вид:

(a, q_i) → q_j,

где . Правило перехода задает переход из состояния q_i , когда на входе читается символ a, в состояние q_j.

КА в цикле прочитывает входную цепочку слева направо, на каждом шаге читается очередной символ. В начале работы КА находится в начальном состоянии. На каждом шаге производится переход в новое состояние в соответствии с правилами перехода. Работа КА завершается, когда цепочка прочитана до конца. Если при этом автомат находится в одном из заключительных состояний, то такая входная цепочка считается успешно распознанной. Если же цепочка прочитана до конца, но КА не находится ни в одном из заключительных состояний, то такая входная цепочка считается нераспознанной. В процессе работы может оказаться, что для некоторого очередного символа текущего состояния КА нет соответствующего правила перехода. В этом случае КА попадает в тупик, и входная цепочка также считается нераспознанной.

Если множество правил перехода таково, что для каждой пары (a, q_i) имеется не более одного правила, то КА называется детерминированным (ДКА) или однозначно определенным. Если же найдется хотя бы два разных правила перехода с одинаковыми парами (a, q_i), то КА называется недетерминированным (НКА), его работа существенно усложняется, так как придется одновременно отслеживать не одно, а несколько текущих состояний КА.

Дата добавления: 2015-07-26; просмотров: 141; Нарушение авторских прав

Мы поможем в написании ваших работ!