Недетерминированные конечные автоматы.
Основные понятия теории автоматов.
Алфавитом Ʃ называют конечное непустое множество символов. Наиболее часто используемые алфавиты:
1) Ʃ = {0,1} – бинарный или двоичный алфавит;
2) Ʃ = {a,b,…,z} – множество строчных букв англ. алфавита.
3) Множество ASCII-символов или множество всех печатных ASCII-символов.
Цепочка или слово – это конечная последовательность символов некоторого алфавита. Например, 01101 – цепочка в бинарном алфавите Ʃ = {0,1}.
Длина цепочки равняется количеству символов в этой цепочке.
Пустая цепочка Ɛ – цепочка, не содержащая ни одного символа, её длина равно нулю.
Степень алфавита: Ʃk – множество всех цепочек длины k, состоящих из символов алфавита Ʃ.
Пусть x и y – цепочки. Тогда xy обозначает их конкатенацию (соединение), т.е. цепочку, в которой последовательно записаны цепочки х и у. Если x- цепочка из i символов: x=a1a2..ai, а у – из j: y=b1b2..bj, то xy – это цепочка длины i+j: xy=a1a2..aib1b2..bj.
Множество цепочек, каждая из которых принадлежит Ʃ*, где Ʃ – некоторый фиксированный алфавит, называют языком. Если Ʃ – алфавит, и L ⊆ Ʃ*, то L – это язык над Ʃ, или в Ʃ.
Детерминированные конечные автоматы.
Детерминированный конечный автомат состоит из следующих компонентов:
1) Конечное множество состояний Q.
2) Конечное множество входных символов Ʃ.
3) Функция переходов δ, аргументами которой являются текущее состояние и входной символ, а значением – новое состояние. Если q – состояние и a – входной символ, то δ(q,a) – это состояние p, для которого существует дуга, отмеченная символом a и ведущая из q в p.
4) Начальное состояние q0, одно из состояний в Q.
5) Множество заключительных, или допускающих, состояний F. Множество F является подмножеством Q.
ДКА часто трактуется как пятёрка: A=(Q, Ʃ, δ, q0, 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,q0)= δ^(a, δ^(x,q0))
Язык, допускаемый L(A)={W| δ^(w,q0)=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) Начальное состояние q0, одно из состояний в Q.
5) Множество заключительных, или допускающих, состояний F. Множество F является подмножеством Q.
НКА часто трактуется как пятёрка: A=(Q, Ʃ, δ, q0, F).
Пример: автомат допускает строки, заканчивающиеся на 0 или 1, но хотя бы один раз вводится 01.
Расширенная функция перехода для НКА:
δ^((Ɛ,q)=q; w=xa; δ^(x,q0)={p1,p2,…,pk}; δ^(w,q0)= 
Язык, допускаемый L(A)={W| δ^(w,q0) 