Лекции Русакова (1021002), страница 15

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 15)

an : (q, γ) ├* (q′, γ′), если справедливо, что:ai : (qi, γi) ├ (qi+1, γi+1), 1 ≤ i ≤ n,где ai ∈ V, γi = γ1, γ2,..., γn+1 = γ′∈Vм* ; qi = q1, ..., qn+1 = q′∈ Q.4.09. Бесконтекстные(контекстно-свободные)языки.Существует два способа определения языка, допускаемого магазиннымавтоматом.Согласно первому способу считается, что входная цепочка α ∈ V*принадлежит языку L1(M) тогда, когда после просмотра последнего символа,входящего в эту цепочку, в магазине автомата М будет находиться пустаяцепочка ε.То есть:L1(M) = { α | α : (q0, z0) ├* (q, ε)}, где q ∈ Q.Согласновторомуспособу,считается,чтовходнаяцепочкапринадлежит языку L2(M) тогда, когда после просмотра последнего символа,входящего в эту цепочку, автомат М окажется в одном из своихзаключительных состояний. Другими словами,L2(M) = { α | α : (q0, z0) ├ * (q f, γ)}, где γ∈Vм* , qf ∈ F.141Доказано, что множество языков, допускаемых произвольнымимагазиннымиавтоматамисогласнопервомуспособу,совпадаетс множеством языков, допускаемых согласно второму способу.Доказано также, что если L(G2) – бесконтекстный язык, порождаемыйграмматикой G2 = (VN, VT, P, S), являющейся формой произвольнойбесконтекстнойграмматикиG,тосуществуетнедетерминированныймагазинный автомат М, такой, что L1(M) = L(G2).При этомМ = (V, Q, Vм, δ, q0, z0, 0),где V = VT; Q = {q0}; Vм = VN ; z0 = S, а для каждого правила G2 видаА → а α, а ∈VТ,α ∈VN* строится команда отображения δ:(q0, а, А) → (q0, α).Аналогично,длялюбогонедетерминированногомагазинногоавтомата М, допускающего язык L1(M), можно построить бесконтекстнуюграмматику G такую, что L(G) = L1(M).Если для конечных автоматов детерминированные и недетерминированные модели эквивалентны соответствующему классу допускаемыхязыков, то этого нельзя сказать в отношении магазинных автоматов.Детерминированные автоматы с магазинной памятью допускают лишьнекотороеподмножествобесконтекстныхязыков,детерминированными бесконтекстными языками.142которыеназывают4.10.

МодельдискретногопреобразователяГлушкова В. М.Определение.Дискретныйпреобразовательпредставляетсобойабстрактныйавтомат А, функционирующий по соответствующим законам в дискретномвремени.Определение.Абстрактный автомат А задается совокупностью шести объектов:А = (Х, Y, Q, q0, δ, λ),где Х – конечное множество входных сигналов, называемое входнымалфавитом автомата;Y – конечное множество выходных сигналов, называемое выходнымалфавитом автомата;Q – произвольное множество, называемое множеством состоянийавтомата;q0 – элемент из множества Q, называемый начальным состояниемавтомата;δ(q, x) и λ(q, x) – две функции, задающие однозначные отображениямножества пар (q, x), где q∈Q и x∈X, в множества Q и Х.

Функция δ(q, x)называется функцией переходов автомата, а функция λ(q, x) – функциейвыходов, либо сдвинутой функцией выходов.Определение.Автомат, заданный функцией выходов, называется автоматом первогорода; автомат, заданный сдвинутой функцией выходов, – автоматомвторого рода.143Абстрактныйавтоматфункционируетвдискретномвремени,принимающем целые неотрицательные значения t = 0, 1, 2, … В каждыймомент t этого времени он находится в определенном состоянии q(t) измножества Q состояний автомата, причем в начальный момент времени t = 0автомат всегда находится в своем начальном состоянии q0 , т.

е. q(0) = q0.В момент времени t, отличный от начального, автомат способенвоспринимать входной сигнал x(t) – произвольную букву входногоалфавита Х и выдавать соответствующий выходной сигнал y(t) – некоторуюбукву выходного алфавита Y.Определение.Закон функционирования абстрактного автомата первого родазадается уравнением: q(t ) = δ (q(t − 1), x (t )) y (t ) = λ (q(t − 1), x (t )),где t = 1,2, .Определение.Закон функционирования абстрактного автомата второго рода –уравнением:q(t ) = δ (q(t − 1), x (t )),()(()())λyt=qt,xtгде t = 1,2, .Таким образом, в абстрактной теории автоматов входные и выходныесигналы рассматриваются как буквы (символы) двух фиксированных для144данного автомата алфавитов.

Абстрактная теория изучает те переходы,которые претерпевает автомат под воздействием входных сигналов вдискретные моменты времени, и те выходные сигналы, которые он при этомвыдает.4.11. Понятиеобабстрактномавтоматеииндуцируемом им отображении.Определение.Сущностьиндуцируемыхабстрактнымавтоматомотображенийзаключается в реализации некоторого отображения ϕ из множества словвходного алфавита в множество слов выходного алфавита.Определение.Отображение реализации некоторого отображения ϕ реализуетсяследующим образом:каждое слово p = xi1, xi2, …, xik входного алфавита X = (x1, x2, …, xn)или, более кратко, каждое входное слово, последовательно, буква за буквой,подается на вход данного абстрактного автомата А, установленногопредварительно в начальное состояние.Возникающая таким образом конечная последовательность входныхсигналов x(1) = xi1, x(2) = xi2, …, x(k) = xik на основании законафункционирования автомата вызывает появление однозначно определеннойконечной последовательности s = y(1), y(2), …, y(k) выходных сигналов.

Этупоследовательность будем называть выходным словом, соответствующимвходному слову р.145Относя, таким образом, каждому входному слову р соответствующееему выходное слово s, мы получаем искомое отображение ϕ , а именно,s = ϕ (p).Определение.Построенное указанным способом отображение ϕ будем называтьотображением, индуцированным абстрактным автоматом А.Определение.Два абстрактных автомата с общим входным и выходным алфавитаминазываются эквивалентными между собой, если они индуцируют одно и тоже отображение множества слов входного алфавита в множество словвыходного алфавита.Определение.Предположим, что заданы два абстрактных автомата:А1 (X1, Y1, Q1, q1, δ1(q,x), λ1(q,x)) иА2 (X2, Y2, Q2, q2, δ2(q,x), λ2(q,x)) одного и того же рода.Еслидляэтихавтоматовсуществуютвзаимнооднозначныеотображения: α – отображающее множество X1 на множество X2;β – отображающее множество Y1 на множество Y2; γ – отображающеемножество Q1 на множество Q2;и, если удовлетворяются условия:γ(q1) = q2;γ(δ1(q1, x)) = δ2(γ(q),α(x));β(λ1(q,x) = λ2(γ(q), α(x)) (для любых q∈Q1 и х∈Х1),146то абстрактные автоматы А1 и А2 называются изоморфными.

В этомслучае говорят, что отображения α, β и γ осуществляют изоморфноеотображение одного автомата на другой.Определение.Изоморфные между собой абстрактные автоматы отличаются друг отдруга лишь обозначениями входных и выходных сигналов и состояний.Вабстрактнойтеорииавтоматов,незанимаютсяпроблемамикодирования состояний, а также входных и выходных сигналов, изоморфныеавтоматы считаются одинаковыми и будут заменяться один другим безкаких-либо дальнейших пояснений.Определение.Операция перехода от данного абстрактного автомата к изоморфномуему автомату состоит просто в переобозначении элементов входногоалфавита, выходного алфавита и множества состояний автомата.Определение.Способ сведения автоматов второго рода к автоматам первого рода,рассмотренный ранее, мы условимся называть интерпретацией автоматавторого рода как автомата первого рода.Определение.Обратная интерпретация автомата первого рода как автомата второгорода при сохранении того же самого множества состояний оказывается,вообще говоря, невозможной.147Определение.Произвольные автоматы первого рода, называются автоматами Мили,а частный случай автоматов второго рода, у которых сдвинутая функциявыходов λ(q, x) не зависит от второй переменной х – автоматами Мура.Способы задания автоматов были рассмотрены ранее.

Здесь отметимодну из особенностей задания автоматов. Так, если произвольным образомзаполненная таблица переходов или таблица выходов представляют собойтаблицу переходов или соответствующую таблицу выходов некоторогоабстрактного автомата, то не всякий граф и не всякая автоматная матрицамогут служить графом или матрицей переходов некоторого автомата.Условия и свойства функций переходов автомата.Первое условие связано с однозначностью функций переходов ивыходов и называется – условием однозначности.Соблюдение этого условия требует, чтобы на графе автомата из любойвершины выходило бы не более одной стрелки, обозначенной конкретнымвходным сигналом.Применительно к матрице это условие означает, что в любой ее строкеконкретный входной сигнал должен встречаться не более одного раза.Второе условие, называется условием определенности, требующим,чтобы для любого входного сигнала х из каждой вершины обязательновыходила бы стрелка, обозначенная этим входным сигналом, и чтобы этотвходной сигнал обязательно присутствовал в каждой строке автоматнойматрицы.Определение.Частичным автоматом называется абстрактный автомат, у которогофункция переходов или функция выходов (обычная или сдвинутая), или обе148эти функции определены не для всех пар значений своих аргументов q и х.В отличие от частичных, ранее рассмотренные автоматы назывались вполнеопределенными.4.12.

Автоматные отображения и события.Определение.Отображения,индуцируемыеабстрактнымиавтоматами,будемназывать автоматными отображениями.Всякое автоматное отображение удовлетворяет следующим четыремусловиям автоматности:1. Автоматное отображение осуществляет однозначное отображение(как правило, частичное) множества слов в некотором конечном алфавите Х(входное алфавитное отображение) в множества слов в некотором конечномалфавите Y (выходное алфавитное отображение).2. Область определения автоматного отображения удовлетворяетусловию полноты, то есть вместе с любым содержащимся в ней словом такжесодержатся все начальные отрезки этого слова. Пустое слово всегда входит вобласть определения отображения.3. Автоматное отображение ϕ сохраняет длину слова.

Характеристики

Список файлов лекций