Эквивалентность детерминированных и недетерминированных конечных автоматов.

В общем случае для любого НКА можно построить ДК с количеством состояний zⁿ, где n-количество состояний недетерминированного конечного автомата.

A_N={Q_N, Ʃ_N, δ_N, q_0N, F_N}; A_D={Q_D, Ʃ_D, δ_D, q_0D, F_D}; L(A_N)=L(A_D)

1) Алфавит Ʃ_N и Ʃ_D – совпадают

2) Q_D ⊆ 2Q_N, причем, если какое-то множество состояний недопустимо в НКА, то оно не входит в Q_D.

3) F – множество всех подмножеств, таких, что в пересечении с F_N оно не пусто.

4) Для каждого подмн. мн. символов S ≤ Q_N и входного символа a δ_s(a,s)=

			A     B C   D
→q0 q1 * q2 q0q1 * q0q2 * q1q2 * q0q1q2	q0q1 ∅ q2 q0q1 q0q1q2 q2 q0q1q2	q0 q2 q2 q0q2 q0q2 q2 q0q2

 

При построении ДКА в качестве начального, используется состояние, соответствующее мн. {q₀}. Данное состояние является достижимым.

Пусть S – мн. достижимых состояний, тогда мн. состояний SU{S’(δ_D(S,Q)=S’, S ∈δ, a ∈ Ʃ}. Теорема: Если ДКА D={Q_D, Ʃ_D, δ_D, {q₀}, F_D} построен из N={Q_N, Ʃ, δ_N, q₀, F_N} методом конструкции подмножеств, то их языки совпадают L(D)=L(N).

Теорема2: Язык L допустим некоторым ДКА тогда и только тогда, коггда допустим некоторый НКА.

Алгоритм преобразования НКА а ДКА: 1) Пусть q₀ – нач. состояние НКА, тогда { q₀} – нач. сост. ДКА. Пусть Р – состояние НКА, в которое можно попасть из q₀ по значениям входных символов q₁, q₂,…, q_n, тогда состояния { q₀, r₁, …, r_k, p} являются сост. ДКА, где, r₁, …, r_k – это все состояния, в которые можно попасть из q₀ по любому суффиксу входного слова.

Конечные автоматы с эпсилон-переходами.

Это пятерка вида E=(Q, Ʃ, δ, q₀, F).

δ, Ʃ U [Ɛ]xQ→Q

Пример: автомат, который имеет вещественные числа:

	Ɛ	0..9	.	+,-
→q1 q2 q3 q4 q5	q2 ∅ q5 q5 ∅	q0∅ q2,q3 ∅ q4 ∅	∅ q4 q4 ∅ ∅	q2 ∅ ∅ ∅ ∅

Эпсилон-замыкание некоторого НКА все состояния, по которым можно поспасть из заданного по Ɛ-переходу. ECLOSE(q) содержит состояние q.

Определим расширенную функцию переходов: δ^(w,q₀), δ^(Ɛ,q)=Ɛ(q); Язык: L(E)={w|δ^(w,q₀) ⋂F=∅}; Теорема: язык Lдопускается неким Ɛ-НКА тогда и только тогда, когда он допускается неким ДКА.

Регулярные выражения.

1) Объединение двух языков L и M, обозначаемое L ∪ M – это множество цепочек, которые содержатся либо в L, либо в M, либо в обоих языках. Например, если L = {001, 10, 111} и M={Ɛ, 001}, то L ∪ M = {Ɛ, 10, 001, 111}.

2) Конкатенация языков L и M – это мн. цепочек, которые можно образовать путем дописывания к любой цепочке из L любой цепочки из M. например, если L = {001, 10, 111} и M={Ɛ, 001}, то LM – это {001, 10, 111, 001001, 10001, 111001}

3) Итерация языка L обозначается L* и представляет собой мн. всех тех цепочек, которые можно образовать путём конкатенации любого количества цепочек из L. L* можно представить как бесконечное объединение , где L⁰={Ɛ}, L¹=L и Lⁱ для I > 1 равен LL..L (конкатенация i копий L).

Определим методы построения регулярных выражений.

Константы Ɛ и ∅ являются регулярными выражениями, определяющими языки { Ɛ } и ∅, соответственно, т.е. L{Ɛ}={Ɛ} и L{∅}={∅}.

Если a – произвольный символ, то а – регулярное выражение, определяющее язык {а}, т.е. L(a)={a}.

Переменныя, обозначенная прописной курсивной буквой, например, L, представляет произвольный язык.

Пусть E и F – регулярные выражения, тогда

1) E + F – регулярное выражение, определяющее объединение языков L(E) и L(F), т.е. L(E + F)=L(E) ∪L(F).

2) EF – регулярное выражение, определяющее конкатенацию языков языков L(E) и L(F). Таким образом, L(EF)=L(E)L(F).

3) E* - регулярное выражение, определяющее итерацию языка L(E), таким образом, L(E*)=(L(E))*.

4) (E) – регулярное выражение, определяющее тот же язык L(E), что и выражение E, т.е. L((E))=L(E)

Приоритет операций:

1) *; 2) конкатенация; 3) объединение (+)