Logo GenDocs.ru

Поиск по сайту:  


Загрузка...

Шпоры по теории автоматов - файл ответы.doc


Шпоры по теории автоматов
скачать (401.1 kb.)

Доступные файлы (4):

ответы.doc385kb.31.05.2003 13:27скачать
ОТВЕТЫ(часть Тани).doc579kb.30.05.2003 14:14скачать
шпора1.doc719kb.02.07.2004 02:09скачать
шпора.doc366kb.31.05.2003 13:55скачать

содержание
Загрузка...

ответы.doc

Реклама MarketGid:
Загрузка...
1.Строки.Префиксы, суффиксы, подстроки. Языки.

Строка – это конечная последовательность символов а1, а2,…,аn, каж-й из кот-х принадлежит некоторому конечному алф-ту Σ, при этом символы в строке могут повторяться.

Пустой строкой наз-т ε-строку ее длина-ноль, т.е.без единого символа.(не=пробелу). |x|=m-длина строки, т.е.строка содержит m символов.

Пусть Σ-некот-й алф-т, обозначим Σ* мн-во опред-х над этим алф-м строк. Для Σ={0,1}; Σ*= {ε,0,1,01,11,10,101,…} видно, что н-во Σ* - предс-т собой бесконечное счетное мн-во элем-в, ε-строка всегда  Σ*

Пусть сущ-т строка х Σ* и |x|=m

Пусть сущ-т строка y Σ* и |y|=n, тогда объединение строк ху им.длину |xy|=m+n – конкатенация.

Если х= а1, а2,…,аm; у= b1, b2,…,bn то |xy|= а1а2…аmb1b2...bn

Если некоторая срока z м.б.представлена как объединение строк х и у: z=ху, то строку х наз-т префиксом строки z, а строку у-суффиксом. Если строка z т.ч.ее м/о представить как объединение 3х строк z=xwy, то строка w н-ся подстрокой строки z.

//z=аcab

префиксы: ε,a,ac,aca,acab

суффиксы: ε,b,ab,cab,acab

подстроки: ε,a,b,c,ac,ca,ab,aca,cab,acab

Разв-е теории и ср-в искус.интелекта позволяет надеяться на то, что взаимод-е чел-ка и ком-ра в недалеком будущем буд/т осуществляться на языке, близком к естественному. Но в наст.время, прог-ты в основном описывают задачи на формальных языках, на языках высокого уровня и иногда на ассемблере. Прог-мы, написанные на алгоритмических языках становятся доступными ком-ру, т/о после их трансляции, т.е.преобразования команд выс.ур/ня в машинные инструкции. Теория построения трансляторов базируется на теории формальнх языков, особенно в части синтакс. и семантического разбора. (семантика – смысл, синтаксис – грамматика).

Формальным языком L над алф-ом Σ н-ся произвольное подмн-во мн-ва Σ*.

Если L1 и L2 это 2а формальных языка, то их объединение есть нов.форм.язык, т.ч.L= L1L2{xy| хL1,уL2 }

// L1={0,01} и L2={ε,0,10}значит L= L1L2={0,01,00,010,010,0110}

L0= ε, L1=L, L2=L*L -объединение форм.языка L с самим собой:

^ Замыкание Клини форм.языка L н-ся .Тогда , тогда L*=L+U{ε}, анологично, можно записать замыкание Клини для мн-ва строк.

^ 2. Форма Бэкуса-Наура. Дерево вывода. Синтакс-е и семан-е деревья.

Правила, определяющие мн-ва текстов образ-т сиснтаксис языка, а описание мн-ва смыслов и соответствий м/у текстами и смыслами – семантику языка. Если в ест.языке допуск-ся некорректности в синтаксисе и м.б.понятен смысл предложения, то в формальных языках предложение в первую очередь должно быть правильным синтаксически.

Ф-ла Бэкуса-Наура(БНФ) исп-ся для описания синтаксиса языков прогр-ия, она использует след-щие 4 символа:

  1. ::= присвоить; 2) < - открыть; 3) > - закрыть; 4) | - или

//The man drives a car.

<простое предложение>::=<подфраза сущ-го><глагол><подфраза сущ-го>;

<подфраза сущ-го>::=<артикль><имя сущ-ое>;

<имя сущ-ое>::= man,

<имя сущ-ое>::=car,

<артикль>::=the,

<артикль>::=a,

<глагол>::=drives

Связи, задаваемые ф-лой Б-Н м.б.представлены и графически в виде дерева-вывода:




м/о построить мн-во простых предложений, удовлетворяющих дан.структуре и синтаксически правильных, но не все они буд.им.смысл.( The car drives a man).

^ Разбор арифмет-го выражения.

<выражение>::=<терм>|<выражение>+<терм>|<выражение>-<терм>;

<терм>::= <множитель>|<терм>*<множ-ль>|<терм>/<множ-ль>;

<множ-ль>::=<а|b|c|(<выраж-е>).

E→T|E+T|E-T;

T→F|T*F|T/F;

F→a|b|c|(E).

Дерево вывода:

Семантическое дерево
^ 3.Контексная гр-ка

Рас-м принцип построения синтак-х диаграмм на пр-ре понятия множитель(их строят для разбора синтаксиса языка прогр-ния).

Любой путь по этой диаг-ме проходит ч/з 1н или неск-ко узлов. Узел м.б.прямоугольным или круглым. Каж-у прям-му узлу соотв-ет своя синтакс.диаг-ма, п/э-у такой узел наз-ся нетерминальным. Круг.узел наз-ся терминальным(он больше не раскрывается).
Нетерм.сим-лы – пропис.буквы, термин. – строчные. Всякое дерево вывода начинается с корня S в соответствии с правилами вывода происходит дв-е по ветвям строющегося дерева до тех пор, пока все нетерм-е символы не буд.раскрыты ч/з терм-е. Мн-во терм-х симв-в образуют висящие вершины, если их прочесть слева направо, то получится строка.

^ Контексная гр-ка(К/Г) – это совокуп-ть 4х объектов: G=(N,T,P,S), где N-конеч.мн-во нетерм.симв-в, T-кон.мн-во терм.симв, P-кон.мн-во продук-й вида α→β, где α(NUT)+-без пустой строки, β(NUT)*т.е.м/о получить и пуст.строку, S-начальный символ.

Если строка α(NUT)* за 1н или неск-ко шагов выводится из начального сим-ла S, то такую строку наз-т сентенциальной формой К/Г-ки G.

Сентенцией гр-ки G наз-т произ-ю сентенциальную форму, составл-ю из симв-в мн-ва Т*, т.е.произ.строку терм.сим-в, кот-я м.б.получена из нач-го сим-ла S. Тогда мн-во всех сентенций гр-ки G наз-т языком, пораждаемым гр-кой G и обоз-т L(G).

L(G)={x Т* |SG*х}.

^ 4. Контексно-свободная гр-ка(КС/Г).

В форм.языках чаще всего в левой части продукции испол-ся 1н нетерм-й симв-л, кот-й явл-ся единс-м симв-м слева. К/Г-ка, удовл-щая этому требованию наз-ся КС/Г-ой. Строгое опред-е КС/Г-ки : гр-ка G=(N,T,P,S), в кот-й мн-во Pсодержит продук-ии вида α→β, где αN, β(NUT)*. Трмин КС возник, т.к. люб.симв-л αN в сентанц.форме гр-ки G м.б.раскрыт согластно продукции из α→β,независимо от того, какими строками он окружен внутри самой сент.формы.

КС/Г-ку м/о представить виде дерева вывода. Корнем кот-го явл-ся нач.символ S, строка терм-х симв-в, или сентенция – последов-ть висящих вершин, читаемых в порядке слева направа.Промеж-е узлы дерева – нетерм-е верш-ны.

– если для люб.строки хL(G) все возможные схемы вывода имеют одно и тоже дерево вывода, то гр-ка наз. однозначная КС/Г-кой. (S→AB; A→aA|a; B→bB|b –строка а3b2). Если одной и тойже строке соотв-т разл.деревья, то гр-ка наз.неоднозна-й(S→SbS|ScS|a-строка abaca).

В дан.опред-ии КС/Г-ки ее продукции им.вид: α→β, где αN, β(NUT)*. Значит корректна запись А→ε, где ε-терм.симол. Гр-ка не им-щая ε-прод-ции наз. ε-своб-й. Было бы идеально раб-ть т/о с ε-своб-ми гр-ми. Для преобр-ия гр-ки G в гр-ку G’, кот-я ε-своб-на н/о:

1. объединить все имеющиеся в Р ε-продукции в мн-во Р’.

2. все нетерм.сим-лы, т.ч. АG* ε. Каж.прод-ции из Р’поставим в соотв-ие такую прод-цию, что в ее прав.части, посрав-ию с исход-й прод-ей Р опущены неск-ко нетермин-х сим-в.

// S→[E]|E;

E→T|E+T|E-T;

T→F|T*F|T/F;

F→a|b|c|ε.

S→[E]|[]|E;

E→T|E+T|E-T|E+|E-|+T|-T|+|-|;

T→F|T*F|T/F|T*|T/|*F|/F|*|/|;

F→a|b|c|.

^ 5. Регулярные языки.

Формулы Бэкуса-Наура, в кот-х правая часть предст-т собой один терм.символ или термин.и нетерм.символы наз-ся регуляр-ми гр-ми. Регул-е гр-ки в процессе компил-ии прогр-мы лишь распоз-т симв-лы языка, после чего н/о испол-ть более сложные процедуры, чтобы осуществить полный грам-й разбор текста прогр-мы.

К/Г-ка G=(N,T,P,S) наз.регул-ой, если:

1.ее продук-ии им.вид А→а или А→аВ, где АN, ВN, аТ.

2.она м/т им.ε-продукцию вида: S→ε и ни одна из др-х продук-й гр-ки G не содержит в своей правой части символа S.

S→аS|aB;

B→bB|b.
S→ε|аS1|aB;

S1→аS1|aB;

B→bB|b.

Если L-регул-й язык, то его замыкание Клини L* так же рег-й язык.

Если L1 и L2- регул-е языки, то L1UL2, L1L2 – также регулярные языки.
^ 7.Пораждающие гр-ки. Виды, примеры.

Пусть дана К/гр-ка G=(N,T,P,S), и есть строка γ1α γ2 (NUT)+, кот.содержит не менее одного термин-го или нетерм-го сим-ла. Если сущ-ет вывод α →β, то в дан.строке α м/о заменить на β – получится новая строка γ1βγ2. След-но, 2-ая строка выводится из 1-ой или 1-ая строка пораждает 2-ю.

Если строка α(NUT)* за 1н или неск-ко шагов выводится из начального сим-ла S, то такую строку наз-т сентенциальной формой К/Г-ки G.

Сентенцией гр-ки G наз-т произ-ю сентенциальную форму, составл-ю из симв-в мн-ва Т*, т.е.произ.строку терм.сим-в, кот-я м.б.получена из нач-го сим-ла S. Тогда мн-во всех сентенций гр-ки G наз-т языком, пораждаемым гр-кой G и обоз-т L(G). Концепция пораждения им.вид:

L(G)={x Т* |SG*х}. Символ G*означает, что строка х выводится из нач-го символа S за 1н или неск-ко шагов по правилам гр-ки G.

//G1=({S,A,B},{a,b},P,S); P: S→A|B, A→aA|a, B→bB|b.

G2=({S,B,C},{a,b,c},P,S); P: S→aSBC|aBC, CB→BC, aB→ab, bB→bb, bC→bc, cC→cc.

м/о показать, что гр-ки G1 и G2 пораждают следующие языки:

L(G1)={an|n1}U{ bn|n1} и L(G2)={anbncn|n1}

Иногда 2е различные гр-ки GиG’пораждают один и тот же язык, т.е. L(G)=L(G’). След-но гр-ки GиG’эквивалентны.

// гр-ка G3= ({S,A,B},{a,b},P,S); P: S→aA|bB|a|b, A→aA|a, B→bB|b.эквивалентна гр-ке G1.
^ 8. Классификация языков по Хомскому. Примеры.

Для рассм-ия св-в всего мн-ва гр-к их н/о классиф-вать по опред.признакам. Наиболее эффективной оказалась класс-ия предлож-ая Хомским. Согластно этой классиф-ии все гр-ки делятся на 4 типа: 0,1,2,3.

  1. гр-ка произвольного типа, без ограничений на правила вывода.

  2. если правило вывода прод-ии предст-ет собой α→β, где α=γ1 х γ2, β = γ1 δ γ2 – строки, где γ1и γ2 (NUT)*, хΝ, δ (NUT)+, то такая гр-ка наз.контекстно-зависимой или 1-го типа.

  3. КС/Г-ка, для кот-й все правила вывода им.вид: α→β, где αN, β(NUT)*.

  4. Регулярная(автоматная гр-ка), правила вывода кот-й: А→а, А→аВ, где АN, ВN, аТ.

Пр-ры

  1. G=(N,T,P,S), N={S}, T={a}, P: S→а; S→аaS. – гр-ка 3типа.( аS=S1  S→а; S→аS1, S1→аS)

  2. P: S→аSb; S→аb – 2тип,

  3. Р: S→аBa; S→аBCb; B→b; Bc→аB; cC→c. – 1тип.



^ 9. Регулярные гр-ки и конечный ав-т.

К/Г-ка G=(N,T,P,S) наз.регул-ой, если:

1.ее продук-ии им.вид А→а или А→аВ, где АN, ВN, аТ.

2.она м/т им.ε-продукцию вида: S→ε и ни одна из др-х продук-й гр-ки G не содержит в своей правой части символа S.

S→аS|aB;

B→bB|b.
S→ε|аS1|aB;

S1→аS1|aB;

B→bB|b.

Люб.регулярная гр-ка м.б.представлена направленным графом. Каж.узел помечается симв-м из мн-ва N. Нач.сим-л S помечают стрелкой, конеч-й обозн-т #.

S→аА|bB;

A→aA|a;

B→bB|b.

Направленный граф, кот.имеет 1н начальный узел и 1н или неск-ко конечных узлов наз-ся конечным авт-м.

Детерм.кон.ав-т(ДКА)-кон.ав-т, ни один узел кот-го не имеет одинаково помеченных дуг, соединяющих его с др-ми узлами ав-та. Задается 5объектами: М=(К,Т, t, k1, F),где К-мн-во сост-й ав-та,Т-входной алф-т, t-ф-ция переходов(показ-т как ав-т переходит из одного сост-ия в др-н под Дей-ем вход-х сим-в), k1-нач-е сост-е ав-та, F-мн-во конеч.сост-й.

Недет.кон.ав-т(НКА)-ав-т, в кот.есть хотя бы один узел, с исходящими из него дугами,помеченными одинаковыми симв-ми. След-но,ф-ция переходов t буд.предст-ть не одно, а мн-во знач-й и буд.полной.
^ 11.Авт-ты и теория алгоритмов.

Ав-т-матем.модель реальных дискретных устр-в,кот-я под воздей-ем входных сигналов м/т переходить из одного состояния в др-е и вырабатывать при этом выходные сигналы.

Ав-ты м.б.:

-конечными, бескон-ми

-синхронными, асинх-ми

-детермин-ми, недерм-ми.

конечным авт-м наз. направленный граф, кот.имеет 1н начальный узел и 1н или неск-ко конечных узлов.

Детерм.кон.ав-т(ДКА)-кон.ав-т, ни один узел кот-го не имеет одинаково помеченных дуг, соединяющих его с др-ми узлами ав-та. Задается 5объектами: М=(К,Т, t, k1, F),где К-мн-во сост-й ав-та,Т-входной алф-т, t-ф-ция переходов(показ-т как ав-т переходит из одного сост-ия в др-н под Дей-ем вход-х сим-в), k1-нач-е сост-е ав-та, F-мн-во конеч.сост-й.

Недет.кон.ав-т(НКА)-ав-т, в кот.есть хотя бы один узел, с исходящими из него дугами,помеченными одинаковыми симв-ми. След-но,ф-ция переходов t буд.предст-ть не одно, а мн-во знач-й и буд.полной.

^ Синхронные ав-ты-это ав-ты, кот.совершают переход из одного сост-ия в др-е в четко опред.момент времени, кот.задается внешним устр-вом(оно генерирует тактовые сигналы(ТС), имеющие постоян-ю длительность и постоянную частоту). Входные сигналы м/т воздействовать на автомат лишь при наличии сигнала ТС и не изменяются в течение его длительности.

В асинх-м ав-те нет внеш-х устр-в, длительность интервала времени, в течение кот.остается неизменным состояние входных сигналов, явл-ся величиной переменной и определяется временем, необходимым ав-ту для установки соответствующих выходных сигналов и завершения перехода в новое состояние, т.е.переходы осущ-ся в те моменты времени, когда выполнены условия для выполнения переходов.

Общая Теория ав-в делится на абст-ю и струк-ю. ^ Абстр-я теория изучает мат-е модели ав-в, реакции ав-в на входные цепочки(выход-е цеп-ки). В абстр-й теории иссл-т т/о матем-е модели и закон-ти, а конкретные структуры не рассматр-ся. В струк-й теории исслед-ся конкрет-е структуры ав-в, способы реализации ав-в на некот-х элемен-х компонентах, кодирование сост-й и т.д.

^ 10.Распознование мн-в ав-ми.

12.Распознователи –задачи, виды распоз-лей.

Распознователи-это ав-ты, которые имеют т/о два выхода допустить или отвергнуть. Цепочка символов входного алф-та допуск-ся распоз-лем, если под действием этой цепочки ав-т, начавший работу в своем начальном состоянии делает ряд переходов приводящих к выходу допустить, в противном сл-е цепочка отвер-ся. Задача распоз-ля – распознать цепочку входных символов, если она правильная-допустить, если нет –отвергнуть.

Распознователями м/т быть конечные детерм.ав-ты, конечные недетерм.ав-ты, МП ав-ты.

1). Пусть конеч.ав-т обнаруживает слово them.

Это ав-т должен иметь 5разл.состояний,каж-е из кот-х предс-т собой позицию в слове them, эти позиции соответствуют префиксам этого слова от пустой цепочки (никакая позиция в слове еще не достигнута) до целого слова. На каждом шаге читается часть слова. Входным сигналам этого ав-та соотв-ют буквы. Состояние, обозначенное символом Them достигается, когда введено все это слово, т.к.задачей данного ав-та явл-ся распознование именно слова them, то последнее состояние явл-ся единственным допускающим состоянием.

2).МП-ав-ты м/т распозновать различные цепочки символов, напр-р цепочки скобок: когда встреч-ся левая скобка в магазин вталк-ся символ А, правая скобка-символ А вытал-ся из маг-на. Цепочка отвер-ся, если во входной строке остались правые скобки, а магазин уже пуст или если цеп-ка еще не до конца прочитана, а в маг-не есть сим-лы А(т.е.лишние левые скобки). Цеп-ка допуск-ся, если к моменту окончания вход.строки маг-н пуст.

МП-ав-ты м/т также распознавать цепочки 3х видов:

1.{1n0n|n>1} начал.отрезок цепочки, состоящий из нулей, втал-ся в магазин. Далее каж.раз, когда во входной цеп-ке встреч-ся 1ца из маг-на выт-ся 1н ноль. Если кол-во 1ц=кол-ву нулей во вход.цепочке, она допуст-ся. Все остальные комбинации б/т отвергнуты.Для реализации дан-й схемы введем спец-й маг-й символ z, кот-й соотв-ет нулю входной цепочки. Дан.ав-т должен работать в двух состоя-х:

S1-втал-е сим-ла z в маг-н(сим-л z долж.быть в маг-не столько сколько нулей),S2-вытал-е сим-в z из маг-на при поступ-ии очередной 1-цы на входе. В сл-е, когда на S2 появится ноль цепочка сразу отверг-ся.

// 000111

▼ S1 000111

▼z S1 00111

▼zz S1 0111

▼zzz S1 111

▼zz S2 11

▼z S2 1

▼ S2

допустить.

2.{1n0m|nm>0}осн.задача-перевод произв.цепочки 0и1ц в упорядоченную цеп.вида: 1n0m. Здесь испол-ся возможность МП ав-та преобразования вход-х цепочек в выходн-е.

3.{w,wr}- 1101|1011: 1301.
^ 13.Машина Тьюринга. Вычисление функций МТ-га.

В 30е гг ХХ века Тьюринг исследовал абстрактную машину, кот.в обл-ти выч-й обладала всеми возможностями совр.выч.машин. Целью его исследования было определить границу м/у тем, что м/т делать выч.маш-а и что не м/т, он пришел к выводу, что вычислитель подобен чел-ку, производящему большое кол-во операций и обладающий большим объёмом памяти. Пол-ые им рез-ты лежат в основе построения совр.ПО и совр.комп-в.

С помощью МТ можно произвести любое выч-е, т.к. любой матем-й процесс м.б.преобразован в алгоритм для МТ-га, но иногда это становится невыгодным. Если для задачи нельзя построить алгоритм, то нельзя построить и МТ-га. Алгоритмом МТ-га называется конечный, содержащий в себе хотя бы одну команду список команд МТ-га.

Структура МТ

МТ-га - модель математического устройства, порождающего вычисл-е процессы. МТ нах. в одном из мн-ва состояний Q={q1,q2,q3,…,qn},это мн-во обозначает кол-во операций, которые м/т выполнять МТ, где q1- начальное состояние; qz- конечное состояние (Пассивное); состояния, отличные от qz- активные.

МТ состоит из абстрактной бесконечной в оба конца ленты, разделенной на секции (ячейки) одинакового размера, и каретки(устр-ва обращения к ленте). В каждой из ячеек м.б.записана или метка(1н из сим-в входного алфавита), или "пустой" символ. Пустой символ (или пробел) при записи в ячейку стирает записанную в ней информацию. Распределение меток по ленте составляет состояние МТ-га. Каретка с помощью записывающей или считывающей головки обрабатывает ленту. В зависимости от того, в каком состоянии нах-ся МТ, и какой символ нах-ся в поле зрения головки, в ячейку записывается новый символ. Каретка м/т двигаться по ленте влево или вправо, ставить метки или стирать их, а также распознавать состояние ячейки на текущий момент времени. Также имеется ф-ия, показывающая направление(знак) сдвига.

Состояние МТ-га в следующий момент времени определяется ее состоянием в данный момент времени (меткой, воспринимаемой в данной ячейке) и командой, соответствующей данному моменту времени. МТ-га реагирует т/о на команды, составляющие алгоритм ее работы:

· стереть метку, · поставить метку, · распознать состояние ячейки, · сдвинуться вправо, · сдвин-ся влево, · остановиться.

^ 14.Магазинный автомат(МП).Определение, структура, задание ав-та.

Обработка входной цепочки МП ав-ом(ав-м с Магаз.памятью) как и в сл-е конеч-х ав-ов, осуществляется за ряд мелких шагов.В отличае от кон.ав-та, МП ав-т м/т обрабатывать 1н символ в течение неск-ких шагов. На каж-м шаге управ-щее устр-во МП ав-та принимает решение: закончить ли обр-ку входного символа(и передти к след-му) или продолжить обр-ку текущего.Структура МП ав-та состоит из:

А




0

1

0

1



В




Входн.строка

С







А

состояние



Магазин







▼-маркер дна магазина, -маркер конца строки.

Сис-ма организации маг-ой п-ти осущес-ся по принципу: LIFO-Last In Fist Out.

Каждый шаг обработки задается правилами(их совокупность наз-т Устр-ом управ-я), использующими инф-цию об: состоянии, верхнем символе маг-на, текущем входном символе.

Переход авт-та в новое состояние вкл-т в себя 3 операции:

1.Операции над магазином:

вталкивание в магазин опред.маг-го символа, выталкивание верхнего сим-ла из маг-на, не изменять магазин.

2.Операции над состоянием:

переход в заданное новое состояние.

3.Операции над входом:

Переход к след-му входному символу(сделать его текущим), не изменять входной сим-л(т.е.перейти и держать).

Детермин-й МП ав-т задается 5 объектами:

1.кон.мн-во входных сим-в, включая маркер конца строки.

2.кон.мн-во магаз-х сим-в, вкл-я маркер дна.

3.кон.мн-во состояний, вкл-я начальное

4.управ-щее устр-во(УУ). УУв каж-й комбинации входного сим-ла, состояния и маг-го сим-ла ставит в соотв-е выход или переход. Выход означает завершение работы, переход-выполнение операции над магазином, сост-ем и входом.

5.начальное содержимое маг-на. Если маг-н пуст, то в его верхушке нах-ся маркер дна, в нач.сост-ии в маг-не м/т нах-ся и некот-е маг-нные сим-лы.

Пусть МП ав-ту н/о распознать цепочку скобок.

1.вход-е мн-во { (,),}

2.мн-во маг-х сим-в {A,▼}

3.мн-во сост-й {S}

4.переходы:

(,А,S = втл(А), сост.(S), сдвиг

(,▼,S = втл(А), сост.(S), сдвиг

),А,S = выт, сост.(S), сдвиг

),▼,S = отвергнуть

,А,S = отвергнуть

,▼,S = допустить.

//сост(S)-перейти в сос-е S.

//Сдвиг-текущим станов-ся сл-й сим-л входной строки.

5.начал-е сост-е маг-на ▼




(

)



А

Втл(А)

сдвиг

Выт

сдвиг

Отверг.



Втл(А)

сдвиг

Отверг.

Допуст.



^ 15.Детермин-й МП ав-т. Распознование цепочек.

Аналогично детер-м и недетер-м конечным авт-м сущ-т детер-е и недет-еМП-авт-мы.Детерминизм ав-ов проявл-ся в том, что на каждую комбинацию состояния входного сим-ла и верхушки стека сущ-т единственная реакция.

МП ав-т наз.распознователем, если у него есть т/о два выхода: допустить или отвергнуть.

Цепочка символов входного алф-та допуск-ся распоз-лем, если под действием этой цепочки ав-т, начавший работу в своем начальном состоянии и с нач-ым содержимым маг-на делает ряд переходов приводящих к выходу допустить, в противном сл-е цепочка отвер-ся.

Расс-м распознавание 3х видов цепочек:

1.{1n0n|n>1}начал.отрезок цепочки, состоящий из нулей, втал-ся в магазин. Далее каж.раз, когда во входной цеп-ке встреч-ся 1ца из маг-на выт-ся 1н ноль. Если кол-во 1ц=кол-ву нулей во вход.цепочке, то когда на входе б/т маркер конца строки, магазин б/т пуст и цепочка допуст-ся. Все остальные комбинации б/т отвергнуты.Для реализации дан-й схемы введем спец-й маг-й символ z, кот-й соотв-ет нулю входной цепочки. Дан.ав-т должен работать в двух состоя-х:

S1-втал-е сим-ла z в маг-н(сим-л z долж.быть в маг-не столько сколько нулей),S2-вытал-е сим-в z из маг-на при поступ-ии очередной 1-цы на входе. В сл-е, когда на S2 появится ноль цепочка сразу отверг-ся.

// 000111

▼ S1 000111

▼z S1 00111

▼zz S1 0111

▼zzz S1 111

▼zz S2 11

▼z S2 1

▼ S2

допустить.

Работа МП ав-та с 2мя сост-ями опис-ся 2 таб-ми:

S1

0

1



z

Сост. S1 Втл(z)

сдвиг

Сост. S2 Выт

сдвиг

Отверг.



Сост. S1 Втл(z)

сдвиг

Отверг.

Отверг.

S2

0

1



z

Отверг.

Сост. S2 Выт

сдвиг

Отверг.



Отверг.

Отверг.

Допуст.

2.{1n0m|nm>0}осн.задача-перевод произв.цепочки 0и1ц в упорядоченную цеп.вида: 1n0m. След-но появится доп.операция-выдать. Н/о выдавать 1цы на выход по мере их появления на входе, а нули складывать в маг-н, когда входная цеп-ка закончится н/о выдать поочередно нули, сохраненные в маг-не.

// входн.строка им.вид:01011,тогда

▼ 01011

▼0 1011

выдать 1

▼0 011

▼00 11

выдать 1

▼00 1

выдать 1

▼00 

выдать 0

▼0 

выдать 0

▼ 

конец

3.{w,wr}- 1101|1011: 1301. ав-т должен им.2состояния, 1ое длится пока ав-т не натал-ся на сим-л разделения(люб.цифра, разделяющая симметр-е части вход.цепочки). в этом сост-ии 1цы и нули помещают в маг-н. Во 2м сост-ии данные из маг-на вытал-ся и сравнив-ся с сим-ми вход-й цепочки. Цеп-ка допус-ся, если совпадут все маг-ные сим-лы и сим-лы входн.цеп-ки, стоящие после разд.сим-ла. Во всех ост-х сл-ях цеп-ка отверг-ся. Этот ав-т опис-ся 2 таб-ми(т.к.2сост-я ав-та).

S1

0

1

|



0

Сост. S1 Втл(0)

сдвиг

Сост. S1 Втл(1)

Выд.1

сдвиг

Сост. S2

сдвиг

Отверг.

1

Сост. S1 Втл(0)

сдвиг

Сост. S1 Втл(1)

Выд.1

сдвиг

Сост. S2

сдвиг

Отверг.



Сост. S1 Втл(0)

сдвиг

Сост. S1 Втл(1) Выд.1

сдвиг

Сост. S2

сдвиг

Отверг.

S2

0

1

|



0

Сост. S2 Выт

сдвиг

Отверг.

Отверг.

Отверг.

1

Отверг.

Сост. S2 Выт

сдвиг

Отверг.

Отверг.



Отверг.

Отверг.

Отверг.

Допуст.


^ 16.Сеть Петри. События и условия. Маркировка. Переходы. Граф достижимых маркировок СП.

В выч.сис-х часто используют СП для описания разл-х процессов. Осн-ми понятиями явл-ся события и условия. Соб-я-это некоторые действия происходящие в сис-ме. Чтобы в сис-ме произошло соб-е необх/о выполнение выполнение соотв-х условий. Соб-я и условия образуют два мн-ва:

Т={t0,t1,..tr}-мн-во переходов

A={ а01,..аf}-мн-во позиций.

Переходы и позиции связаны ф-ми: I(in)-входная, O(out)-выходная.

СП задается 4 объектами: N=(A,T,I,O)

СП задается при помощи графов, кот-е содержат два типа вершин:позиции(кружки) и переходы(вертикальные черточки), соединяют вершины различных типов направленные дуги.

Маркировка СП показывает в каких позициях нах-ся метки. Позиция СП содержит метку, если поставленное в соответствии с этой позицией условие выполнено, и не содержит в противном сл-е.Т.о.маркир-ая СП задается 5 объектами: N=(A,T,I,O,Мо), где Мо-вектор начальной маркировки. Распределение меток в позиции графа определяют порядок выполнения переходов. Переход м.б.реализован т/о тогда, когда он становится активным(т.е.все его входные позиции им.метки-их наз.разреш-ми). в рез-те выполнения перехода все разрешающие метки стираются, а все выходные позиции дан.перехода получают метки. След-но после перехода маркировка меняется.

Мо={10001}, M1={01101},где М1-непосредственно достижимая метка из Мо.

^ 17.Классификация сетей Петри. Применение СП в теории ав-в.

1.автоматные графы-это СП с 1ой входной и 1ой выходной дугой из каждого перехода.

2.Маркированные графы-Сп с ограничением на число входных и выходных переходов и позиций.

3.Чистые СП

4.Сеть свободного выбора. Им.ограничение:каж-я выходная дуга от позиции явл-ся или ее единственным выходом или ее един-м входом перехода.

5.Простая СП. Отличается наличием у каж-го перехода не более чем 1й входной позиции, имеющей более одного выхода.

6.Устойчивые СП.




Исходные СП (вышеперечисленные)указывают лишь на возможность реализации послед-ти переходов без учета времени переходов. Расширенные СП содержат доп.объекты, позволяющие учесть время переходов, вероят-ти переходов и т.д.

1.Временные СП. Описыв-ся 7объектами: Ns=(A,T,I,O,Mo,,ν), Где =(τ12,... τi)временная база.

ν: А*→,ф-ция временных задержек.

В эти сети вводится пассивное состояние метки в позициях: если в позицию поступает метка, то она не м/т учав-ть в возбуждении перехода, в течении опред.времени.

2.Стахостические СП. Временные сети, у которых каж.дуге соответ-т вер-ть блуждания метки в сети.

3.Маркированные СП. Вводят вектор состояния сети и выполняют расчет вер-ти нахождения сети в каждом состоянии, т.о.описывают структуру сис-мы.

4.Нагруженные СП. Испол-т для представления ресурсов, алгоритмов, прог-мм, процессов.

5.Логические СП. Разновидность Нагр.СП(4) описывают структуры данных, ф-ции и алгоритмы управ-я. Действия соотв-т логич-м ф-циям.

6.Структурированные СП. Испол-т описание сис-мы виде совокупности элем-в, хранящихся в базах данных.

7.Составные СП. Содержат модули из сетей различного типа.

Из расширенных СП выделяют два типа:

^ 1.Сеть Мерлина

Ns=(A,T,I,O,Mo,λ*** ), где λ*={τi*}это мн-во временных интервалов, обозначающих миним-ю задержку на дан.переходе. λ***={τi**}-это набор временных интервалов, обозначающих максим-е время задержки на каж.переходе.Т.о.время выполнения i-го перехода лежит в пределах: τi* ti τi**.

2.Однозначные(Е-сети).

NЕ=(A,Ар,АR,Т,Mo),где А-мн-во позиций, Ар-мн-во перефирийных позиций, АR-мн-во решающих позиций, Т-мн-во переходов. Каж.переход описывается мн-вом объектов: ti=(S,τ(ti),ρ), где S-тип перехода, τ(ti)-время перехода, ρ-процедура перехода.

На базе СП м/о строить мин.ав-ты, если заменить нетерм-е сим-лы гр-ки на позиции, а терм-е на переходы.

В СП две позиции м.б.соеденены м/у собой т/о ч/з преходы, а переходы ч/з позиции. Т.е.в некоторых сл-ях н/о вводить доп-е позиции, кот-е будут соотв-ть введенным нетер-м симв-м.

//S→abA



^ 18.Эквивалентность авт-в

Для каж-го конеч.ав-та сущ-т бескон-е кол-во др-х конеч-х ав-в, кот-е распоз-т те же цепочки. Но сущ-т единс-й кон.ав-т, кол-во состояний кот-го минимально. Два состояния наз.эквивалентными, если они одинаково реагируют на все продолжения входных цепочек. Состояние S конечного распоз-ля М экв-но сост-ю t кон-го распоз-ля N тогда и т/о тогда, когда авт-т М, начав работу в сост-ии S б/т допускать те же цепочки, что и ав-т N, начав работу в сост-ии t.

Из опред-ия эквив-х сост-й м/о дать опред-е экв-х авт-в: ^ Авт-ты М и N экв-ны,тогда и т/о тогда, когда экв-ны их начальные состояния.

Проверка экв-ти сост-й основывается на:

1.условие подобия, т.е.сост-я S и t должны  или к допуск-м, или к отвергающим.

2.условие приемственности, т.е.для всех входных сим-в, сост-я S и t должны переходить в др-е эквивал-е сост-ия, т.е.их приемники д.б.эквив-ными.

(метод№1):метод таблиц экв-х сост-й.





0

1




0

5

2

0

1

6

2

0

2

0

4

0

3

3

5

0

4

6

2

1

5

3

0

1

6

3

1

1

А

0

1

(0,1)

(5,6)

2

(5,6)

3

(0,1)
1.строется таблица эквив-сти сост-й(А), первыми запис-ся два начал-х сост-я, кот-е подверг-ся анализу.

2.выбирается строка в дан.таблице, ячейки кот-й еще не заполнены и проверяется подобны ли состояния, кот-ми она помечена. Если сост-я не подобны, то два исходных сост-я не эквив-ны и процесс завершен, если подобны, то вычисляется рез-т применения каж-го вход-го сим-ла к этой паре сост-й и записыв-сяполученные пары сост-й.

3. если пара разл-х сост-й(получ-х на 2 шаге) еще не использ-сь как метка, то она перепис-ся на новую строку.

4. если таблица завершена выписыв-ся все состояния, поражденные в ходе проверки,кот.б/т экв-ми сост-ми. В нашем пр-ре 0~1 и 5~6.

Сущ-т еще 1н метод №2:метод разбиения на непересекающиеся подмн-ва.





0

1




0

5

2

0

1

6

2

0

2

0

4

0

3

3

5

0

4

6

2

1

5

3

0

1

6

3

1

1
1.все мн-во сос-й разбив-ся на 2 блока, 1н блок содержит т/о отверг-е, др-й т/о доп-щие сост-ия. Ни олно сост-е 1-го блока не м.б.экв-но как.либо состоянию из 2-го блока.

Р1=({0,1,2,3},{4,5,6})

2.расс-м переходы в 1м блоке под возд-ем 0. из сост-й 0и1 переход в 5и6- доп-щие сост-ия, из 2и3 переход в 0и3-отверг-е сост-я, значит Р2=({0,1},{2,3},{4},{5,6}).

3.расс-е поведение блока {2,3} если на входе дей-т серия сим-в 0: они не экв-ны, Р3=({0,1},{2},{3},{4},{5,6}).

4.дальнейшие попытки разбить блок ={0,1}и {5,6}ничего не дают, значит 0~1 и 5~6.
^ 19.Минимизация абстр-х ав-ов(методы и примеры).

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

(метод№1):метод таблиц экв-х сост-й.





0

1




0

5

2

0

1

6

2

0

2

0

4

0

3

3

5

0

4

6

2

1

5

3

0

1

6

3

1

1

А

0

1

(0,1)

(5,6)

2

(5,6)

3

(0,1)
1.строется таблица эквив-сти сост-й(А), первыми запис-ся два начал-х сост-я, кот-е подверг-ся анализу.

2.выбирается строка в дан.таблице, ячейки кот-й еще не заполнены и проверяется подобны ли состояния, кот-ми она помечена. Если сост-я не подобны, то два исходных сост-я не эквив-ны и процесс завершен, если подобны, то вычисляется рез-т применения каж-го вход-го сим-ла к этой паре сост-й и записыв-сяполученные пары сост-й.

3. если пара разл-х сост-й(получ-х на 2 шаге) еще не использ-сь как метка, то она перепис-ся на новую строку.

4. если таблица завершена выписыв-ся все состояния, поражденные в ходе проверки,кот.б/т экв-ми сост-ми. В нашем пр-ре 0~1 и 5~6.

Метод поиска экв-х сост-й №1 (метод таблиц экв-х сост-й) не всегда применим,т.к.расс-ся т/о пары экв-х сост-й и каж-й раз для новой пары сос-й н/о строить свою таблицу.

Метод №2:метод разбиения на непересекающиеся подмн-ва.





0

1




0

5

2

0

1

6

2

0

2

0

4

0

3

3

5

0

4

6

2

1

5

3

0

1

6

3

1

1
1.все мн-во сос-й разбив-ся на 2 блока, 1н блок содержит т/о отверг-е, др-й т/о доп-щие сост-ия. Ни олно сост-е 1-го блока не м.б.экв-но как.либо состоянию из 2-го блока.

Р1=({0,1,2,3},{4,5,6})

2.расс-м переходы в 1м блоке под возд-ем 0. из сост-й 0и1 переход в 5и6- доп-щие сост-ия, из 2и3 переход в 0и3-отверг-е сост-я, значит Р2=({0,1},{2,3},{4},{5,6}).

3.расс-е поведение блока {2,3} если на входе дей-т серия сим-в 0: они не экв-ны, Р3=({0,1},{2},{3},{4},{5,6}).

4.дальнейшие попытки разбить блок ={0,1}и {5,6}ничего не дают, значит 0~1 и 5~6.
Недостижимым наз. состояние, в которое нельзя попасть из нач-го сост-ия ни при какой входной цепочке. Из таблицы, задающей ав-т н/о установить недостиж-е состояния и устранить их как бесполезные. Иногда эти состояния видно сразу, но чаще необх-мо выполнить сл-й алгоритм, чтобы выявить эти сост-ия:

  1. начать список с начал-го состояния.

  2. для каж-го сост-ия, уже внесенного в список, добавить все еще не занесенные в него сос-ия, кот-е м.б.достигнуты под Дей-ем как.либо из входных сим-в.

  3. если эта процедура перестает пораждать нов-е состояния, то алг-м завершен и все сост-ия, кот.не проявились по ходу алг-ма не достижимы, соответ-щие строки удаляются.




0

1










0

1




0

4

3

0




0

4

3

0

1

2

5

1




4

2

3

1

2

3

6

0




3

0

2

0

3

0

2

0




2

3

6

0

4

2

3

1




6

3

6

0

5

0

4

1
















6

3

6

0
















Недостиж-е сост-ия: 1,5


^ 20. Соединения ав-ов: последовательное, парал-ое, с обр.связью.

Ав-ты м/т соединяться др.с др-м, образуя более сложные устр-ва. Сущ-т 3 вида соединения: последовательное, парал-ое, с обр.связью.

1.парал-ое соед-е.

Н/о найти эквив-й автомат Sэ, зная описание каж-го из ав-в и схемы φ, вырабат-щей выходной сигнал.

S1=(А1, z,w111, a01)

S2=(А2, z,w222, a02)

φ! SЭ=(А, z,w,δ,λ, a0)-?

А=А12111 а12, А221 а22 )= а11 а21, а11 а22, а12 а11, а12 а22. схема φ явл-ся комбинац-й и сост-й не пораждает.

Пр-р построения Sэ.


α/S1

а11

а21

а31

Z1

а11/w'1

а21/w'2

а31/w'2

Z2

а31/w'1

а31/w'1

а21/w'1

β/S2

а12

а22

Z1

а12/w''1

а22/w''2

Z2

а22/w''2

а12/w''1

φ

w'1

w'2

w''1

w1

w2

w''2

w2

w3


Состояния Sэ: а11 а211, а11 а222, а21 а123, а21 а224, а31 а125, а31 а226.


SЭ

а1

а2

а3

а4

а5

а6

Z1

а11а12/w11/w1
















Z2










а31а12/w15/w1








2.Последовательное соединение.

S1=(А1, z1,w111, a01)

S2=(А2, z2,w222, a02)

А=А12

Z2=w1 и w=w2


α/S1

а11

а21

а31

Z1

а11/w'1

а21/w'2

а31/w'2

Z2

а31/w'1

а31/w'1

а21/w'1

β/S2

а12

а22

w'1

а12/w''1

а22/w''2

w'2

а22/w''2

а12/w''1


Состояния Sэ: а11 а211, а11 а222, а21 а123, а21 а224, а31 а125, а31 а226.

а631 а22, а31/z2=(а21/ w'1)* а22: а21 а22/w''2= а4/w''2


SЭ

а1

а2

а3

а4

а5

а6

Z1



















Z2
















а21 а22/w''2= а4/w''2


3.Соединение с обр-й связью.


S1

а11

а21

а31

р1

а31/w''1

а21/w''2

а21/w''1

р2

а21/w''3

а11/w''1

а11/w''2

S2

w'1

w'2




а12

а22

у1= w''1

а12

а22

у2= w''2

а22

а22

у3= w''3

а12

а12



γ

z1

z2

z3

w'1

p1

p1

p1

w'2

p2

p2

p1



Sэ: а11 а121, а11 а222, а21 а123, а21 а224, а31 а125, а31 а226.

Хотя бы 1н из ав-т долж.быть ав-м Мура( в дан. Сл-е ав-т S2 явл-ся ав.Мура).


SЭ

а1

а2

а3

а4

а5

а6

Z1













а21а12/ w''1=

а3/ w''1




Z2







а21а22/ w''2=

а4/ w''2










Z3



















Если ав-т нах-ся в сост-ии а5,т.е.S1 в сост-ии а31, а S2 в сост-ии а12.S2 в сост-ии а12 выраб-т сигнал w1'кот-й поступает на 2й вход элемента γ. На 1й вход элем-а γ пост-т вход.сигнал из мн-ва z, пусть б/т z1, тогда по таблице γ находим что по z1 и w1'выраб-ся сиг-л р1, кот-й поступ-т на вход ав-та S1. По условию ав-т S1 нах-ся в сост-ии а31. под дейст-м р1 он переходит в а21, выраб-вая при этом w1",кот-й явл-ся одновременно и выходным сиг-м эквив-го ав-та и входным для S2. Ав-т S2, находясь по умолчанию в сост-ии а12 под дейс-м w1" переходит в а12. на этом реакция на дан.вход.сигнал заканч-ся. Окончательно из а5 под дейс-м z1 ав-т переходит в а3 с выроботкой w1".
21.Сеть ав-ов.

Сеть испол-ся как модель, описывающая работу некот-й совок-ти авт-в.

N(net)=(z,{Si},w,{fi},{ψi},g).

1.z входной алф-т

2.{Si}-мн-во полуав-в(базис сети), каж.полуав-т(компонентный ав-т):Si=(Аi,zii), структура кот-го:

zi={zi', zi"}, где zi'-внутрен.вход.алф-т ав-та Si, zi"-внешний вход.алф-т.

Аi -мн-во сост-й

δi -показ-т: zi* Аi → Аi.

3.w-выходной алф-т сети

4.{fi}- мн-во ф-ций соединения полуав-в(структура сети)

5.{ψi}- мн-во входных ф-ций.

6.g- формирователь выходной ф-ции сети.

Обобщенная структура сети:




^ 25. Синтез абст-х ав-ов:исключение недост-х сост-й, минимизация.
При синтезе ав-та н/о учитывать понятие приведенного ав-та-авт-та, в кот.отсутствуют недостиж-е сост-ия и нет эквив-х сост-й, такие ав-ты им-т миним-но возможное число сост-й и более компактно реализ-ся на ЭВМ. Для решения каж.задачи сущ-т единст-й приведенный ав-т. Для его получения н/о исключить недостижимые и эквив-е сост-я из ав-та.

Недостижимым наз. состояние, в которое нельзя попасть из нач-го сост-ия ни при какой входной цепочке. Из таблицы, задающей ав-т н/о установить недостиж-е состояния и устранить их как бесполезные. Иногда эти состояния видно сразу, но чаще необх-мо выполнить сл-й алгоритм, чтобы выявить эти сост-ия:

  1. начать список с начал-го состояния.

  2. для каж-го сост-ия, уже внесенного в список, добавить все еще не занесенные в него сос-ия, кот-е м.б.достигнуты под Дей-ем как.либо из входных сим-в.

  3. если эта процедура перестает пораждать нов-е состояния, то алг-м завершен и все сост-ия, кот.не проявились по ходу алг-ма не достижимы, соответ-щие строки удаляются.




0

1










0

1




0

4

3

0




0

4

3

0

1

2

5

1




4

2

3

1

2

3

6

0




3

0

2

0

3

0

2

0




2

3

6

0

4

2

3

1




6

3

6

0

5

0

4

1
















6

3

6

0
















Недостиж-е сост-ия: 1,5

Для каж-го конеч.ав-та сущ-т бескон-е кол-во др-х конеч-х ав-в, кот-е распоз-т те же цепочки. Но сущ-т единс-й кон.ав-т, кол-во состояний кот-го минимально. Для его получения н/о удалить все экв-е сост-я.

(метод№1):метод таблиц экв-х сост-й.





0

1




0

5

2

0

1

6

2

0

2

0

4

0

3

3

5

0

4

6

2

1

5

3

0

1

6

3

1

1

А

0

1

(0,1)

(5,6)

2

(5,6)

3

(0,1)
1.строется таблица эквив-сти сост-й(А), первыми запис-ся два начал-х сост-я, кот-е подверг-ся анализу.

2.выбирается строка в дан.таблице, ячейки кот-й еще не заполнены и проверяется подобны ли состояния, кот-ми она помечена. Если сост-я не подобны, то два исходных сост-я не эквив-ны и процесс завершен, если подобны, то вычисляется рез-т применения каж-го вход-го сим-ла к этой паре сост-й и записыв-сяполученные пары сост-й.

3. если пара разл-х сост-й(получ-х на 2 шаге) еще не использ-сь как метка, то она перепис-ся на новую строку.

4. если таблица завершена выписыв-ся все состояния, поражденные в ходе проверки,кот.б/т экв-ми сост-ми. В нашем пр-ре 0~1 и 5~6.

Метод поиска экв-х сост-й №1 (метод таблиц экв-х сост-й) не всегда применим,т.к.расс-ся т/о пары экв-х сост-й и каж-й раз для новой пары сос-й н/о строить свою таблицу.

Метод №2:метод разбиения на непересекающиеся подмн-ва.





0

1




0

5

2

0

1

6

2

0

2

0

4

0

3

3

5

0

4

6

2

1

5

3

0

1

6

3

1

1
1.все мн-во сос-й разбив-ся на 2 блока, 1н блок содержит т/о отверг-е, др-й т/о доп-щие сост-ия. Ни олно сост-е 1-го блока не м.б.экв-но как.либо состоянию из 2-го блока.

Р1=({0,1,2,3},{4,5,6})

2.расс-м переходы в 1м блоке под возд-ем 0. из сост-й 0и1 переход в 5и6- доп-щие сост-ия, из 2и3 переход в 0и3-отверг-е сост-я, значит Р2=({0,1},{2,3},{4},{5,6}).

3.расс-е поведение блока {2,3} если на входе дей-т серия сим-в 0: они не экв-ны, Р3=({0,1},{2},{3},{4},{5,6}).

4.дальнейшие попытки разбить блок ={0,1}и {5,6}ничего не дают, значит 0~1 и 5~6.







Скачать файл (401.1 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru