Презентация на тему Лекции КАиФЯ 2-4. Конечные автоматы и формальные языки

представление функции перехода δ(q,a) (в левом столбце - состояния,

в первой строке – символы алфавита)

в соответствие состоянию q и цепочке w состояние p,

в которое попадет автомат из состояния q, обработав цепочку w.
Базис: Индукция: пусть w=xa, тогда

если , то

в соответствие состоянию q и цепочке w множество состояний

p, в которое попадет автомат из состояния q, обработав цепочку w.
Базис: Индукция: пусть w=xa, тогда
если и то

определения)
=
=
Индукция: |w| = n+1, w = xa и

=

пустой цепочке
Неформальное определение ε-НКА
1. Необязательный знак + или – 2.

Цепочка цифр (возможно пустая) 3. Разделяющая десятичная точка . 4. Цепочка цифр (возможно пустая) Цепочки 2 и 4 одновременно не могут быть пустыми

p и существует переход, отмеченный из p в

r, то ECLOSE(q) содержит r.

ECLOSE(1)={1,2,3,4,6} ECLOSE(2)={2,36} ECLOSE(5)={5,7} ECLOSE(4)={4}

из

подмножеств QЕ
2.
3.
4.

него по символам,
отсутствующим на рисунке. У состояния Ø

переход по любому
символу в себя.

Л3-2013
конец

Преобразуем D в
-НКА E. Добавим переходы

для всех состояний автомата D. Преобразуем все в

Достаточность. Пусть некоторый -НКА.
Используем модифицированную конструкцию подмножеств для построения ДКА

Доказать: L(D)=L(E). Покажем:

Базис. |w|=0 => w= . По определению . По определению
начального состояния ДКА D . Для любого состояния p ДКА => => .

Индукция. Пусть , причем и равняются .

Л4-2013
начало

вход: РВ, выход: ДКА
Операции над языками
Объединение языков L и

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

S. C. Kleene)
языка L (L*) представляет множество цепочек,

образованных
путем конкатенации любого (и нулевого) количества цепочек
из L. При этом допускаются повторения цепочек – одна и
та же цепочка может быть выбрана для конкатенации более
одного раза.
L={0,1}, L* - все битовые цепочки, в том числе и пустая
L={0,11}, L* - битовые цепочки, в том числе и пустая,
содержащие четное число единиц
L* = Ui>=0Li, где L0={ }, L1=L и Li=LL…L (конкатенация i копий L)
для i>=0
L={0,11}: L0={ },L1={0,11}, L2={00,011,110,1111} L3={000,0011,0110,01111,1100,11011,11110,111111}
L – множество всех нулевых цепочек: Li=L i>0 => L*=L
Ø*={ }

определяющие языки Ø и { }
если a символ

алфавита, то a РВ, определяющее язык {a} (чаще сам символ используют в качестве РВ)
Индукция:
E и F суть РВ => E+F тоже РВ, определяющее объединение языков L(E) и L(F): L(E) U L(F)
E и F суть РВ => EF тоже РВ, определяющее конкатенацию языков L(E) и L(F): L(E)L(F)
E есть РВ => E* тоже РВ, определяющее итерацию языка L(E): L(E*)=(L(E))*
E есть РВ => (E) тоже РВ, определяющее тот же язык L(E), что и выражение E: L((E))=L(E)

единиц
01 -> {01}
(01)* -> {w: w=(01)n, n>=0}
(01)*+ (10)*+ 0(10)*+

1(01)*
к (01)* допишем слева +1, а справа +0
L( +1)=L( ) U L(1)={ , 1}
( +1)(01)*( +0)

символов слева от нее и являющейся РВ)
Конкатенация (ассоциативная)
Объединение (ассоциативная)
Для

изменения приоритета используются скобки

Пример

01*+1 ⬄ (0(1*))+1 ?

(01)*+1 ?

0(1*+1) ?

РВ, язык которого состоит из множества меток

(цепочек) w, ведущих от состояния i к состоянию j ДКА и не имеющих промежуточных состояний с номерами > k

движение вдоль пути от i к j ->

состояние1

состояниеn

определение от k=0 до k=n
Базис: k=0 (у пути нет

промежуточных состояний)
дуга из i в j
путь длины 0, состоящий из вершины i
=> возможен только первый случай
если таких дуг нет, то
одна дуга, помеченная символом а, то
несколько дуг, помеченных a1,a2,…,ak

i=j => путь длины 0 и петли в состоянии i