Недетерминированные конечные автоматы.

Основные понятия теории автоматов.

Алфавитом Ʃ называют конечное непустое множество символов. Наиболее часто используемые алфавиты:

1) Ʃ = {0,1} – бинарный или двоичный алфавит;

2) Ʃ = {a,b,…,z} – множество строчных букв англ. алфавита.

3) Множество ASCII-символов или множество всех печатных ASCII-символов.

Цепочка или слово – это конечная последовательность символов некоторого алфавита. Например, 01101 – цепочка в бинарном алфавите Ʃ = {0,1}.

Длина цепочки равняется количеству символов в этой цепочке.

Пустая цепочка Ɛ – цепочка, не содержащая ни одного символа, её длина равно нулю.

Степень алфавита: Ʃ^k – множество всех цепочек длины k, состоящих из символов алфавита Ʃ.

Пусть x и y – цепочки. Тогда xy обозначает их конкатенацию (соединение), т.е. цепочку, в которой последовательно записаны цепочки х и у. Если x- цепочка из i символов: x=a₁a₂..a_i, а у – из j: y=b₁b₂..b_j, то xy – это цепочка длины i+j: xy=a₁a₂..a_ib₁b₂..b_j.

Множество цепочек, каждая из которых принадлежит Ʃ*, где Ʃ – некоторый фиксированный алфавит, называют языком. Если Ʃ – алфавит, и L ⊆ Ʃ*, то L – это язык над Ʃ, или в Ʃ.

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

Детерминированный конечный автомат состоит из следующих компонентов:

1) Конечное множество состояний Q.

2) Конечное множество входных символов Ʃ.

3) Функция переходов δ, аргументами которой являются текущее состояние и входной символ, а значением – новое состояние. Если q – состояние и a – входной символ, то δ(q,a) – это состояние p, для которого существует дуга, отмеченная символом a и ведущая из q в p.

4) Начальное состояние q₀, одно из состояний в Q.

5) Множество заключительных, или допускающих, состояний F. Множество F является подмножеством Q.

ДКА часто трактуется как пятёрка: A=(Q, Ʃ, δ, q₀, F).

Цепочка допускается данным автоматом, если после ввода последнего символа цепочки автомат находится в допускающем состоянии: δ^: Ʃ*×Q→Q переход соотв. этому же сост.

Пример: Ʃ = {0,1}. Распознать слова вида {x01y | x,y ∈ Ʃ*}

- начальное состояние

- допускающее состояние

Дуги – символы переходов, подписываются входными значениями

→q0 q1 * q2	q1 q1 q1	q2 q2 q2

определим расширенную функцию перехода: δ^: Ʃ*×Q→Q; q(Ɛ,q)=q; w=xa; δ^(w,q₀)= δ^(a, δ^(x,q₀))

Язык, допускаемый L(A)={W| δ^(w,q₀)=F}

 

Алгебраические законы для регулярных выражений.

L+M=M+L – коммутативность сложения

(L+M)+N= L+(M+N) – ассоциативность сложения

(LM)N=L(MN) - ассоциативность умножения

∅+L=L+∅ - пустой язык является единицей

ƐL=LƐ – является единицей относительно конкатенации

∅L=∅ - пустой язык является нулём относительно умножения

L(M+N)=LM+LN - дистрибутивный закон

(M+N)L=ML+NL - дистрибутивный закон

Недетерминированные конечные автоматы.

Недетерминированный конечный автомат состоит из следующих компонентов:

1) Конечное множество состояний Q.

2) Конечное множество входных символов Ʃ.

3) Функция переходов δ, аргументами которой являются состояние из Q и входной символ из Ʃ, а значением – некоторое подмножество множества Q.

4) Начальное состояние q₀, одно из состояний в Q.

5) Множество заключительных, или допускающих, состояний F. Множество F является подмножеством Q.

НКА часто трактуется как пятёрка: A=(Q, Ʃ, δ, q₀, F).

Пример: автомат допускает строки, заканчивающиеся на 0 или 1, но хотя бы один раз вводится 01.

Расширенная функция перехода для НКА:

δ^((Ɛ,q)=q; w=xa; δ^(x,q₀)={p₁,p₂,…,p_k}; δ^(w,q₀)=

Язык, допускаемый L(A)={W| δ^(w,q₀)