Лекции по дискретке (1021001), страница 13

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

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

Q = {q₀ , q₁, ..., q_n-1} – конечное множество состояний;

q₀ ∈ Q – начальное состояние;

F ⊆ Q – множество заключительных состояний;

δ – функция, отображающая Q x V₂ в множество подмножеств

Q x V₂ x {Л, П}.

Множество V₁ содержит два специальных символа Z_l и Z_p, называемых граничными маркерами, которые не позволяют головке управляющего устройства уйти с той части ленты, на которой задана входная цепочка.

Определение.

Формально линейно-ограниченный автомат является недетерминированной машиной Тьюринга с ограничением на длину цепочки рассматриваемых символов. Ситуация линейно-ограниченного автомата и элементарное действие определяются так же, как и для машины Тьюринга.

Определение.

Язык, допускаемый линейно-ограниченным автоматом, определяется как множество:

L(М) = {α | α∈ (V₁ – { Z_l, Z_p })* ∧ (q₀, Z_l α Z_p, 1) ├ * (q_f, β, i)},

где q_f = F, β ∈ V₂*, 1 ≤ i ≤ n (n – длина исходной цепочки).

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

37.Автоматы с магазинной памятью и бескон­текстные языки.

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

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

В отличие от конечных автоматов, рассмотренных ранее, автоматы и преобразователи с магазинной памятью снабжены дополнительной магазинной памятью (рабочей лентой) (рис. 4.11).

Рис. 4.11. Автоматы с магазинной памятью.

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

1) стереть символ из верхней ячейки (при этом все символы, находящиеся на рабочей ленте, перемещаются на одну ячейку вверх);

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

Таким образом, устройство магазинной памяти можно сравнить с устройством магазина боевого автомата; когда в него вкладывается патрон, те, которые уже были внутри, проталкиваются вниз; достать можно только патрон, вложенный последним.

Определение.

Формально детерминированный магазинный автомат определяется как следующая совокупность объектов:

М = (V, Q, V_м, δ, q₀, z₀, F),

где V, Q, q₀ ∈ Q, F – определяются также, как и для конечного автомата;

V_м = {z₀, z₁, ..., z_p-1} – алфавит магазинных символов автомата;

δ – функция, отображающая множество Q х (V ∪ {ε}) x V_м в множество Q x V_м, где ε – пустая цепочка;

z₀ ∈ V_м – так называемый граничный маркер, т. е. символ, первым появляющийся в магазинной памяти.

Определение.

Недетерминированный магазинный автомат отличается от детерминированного только тем, что значениями функции переходов являются не состояния, а множества состояний, то есть функция δ отображает множество Q х (V ∪ {ε}) x V_м в множество конечных подмножеств Q x V_м .

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

Далее будем рассматривать только недетерминированные магазинные автоматы.

Рассмотрим интерпретацию функции δ для такого автомата. Эту функцию можно представить совокупностью команд вида:

(q, a, z) → (q₁, γ₁), ..., (q_m, γ_m),

где q, q₁, ..., q_m ∈ Q, a ∈ V, z ∈V_м, γ₁, ..., γ_m ∈V_м*.

При этом считается, что если на входе читающей головки автомата находится символ а, автомат находится в состоянии q, а верхний символ рабочей ленты z, то автомат может перейти к состоянию q_i , если записать на рабочую ленту цепочку γ_i (1 ≤ i ≤ m) вместо символа z и передвинуть входную головку на один символ вправо.

Крайний левый символ γ_i должен при этом оказаться в верхней ячейке магазина. Команда (q, ε , z) → (q₁, γ₁), ..., (q_m, γ_m) означает, что независимо от входного символа и, не передвигая входной головки, автомат перейдет в состояние q_i, заменив символ z магазина на цепочку γ_i (1 ≤ i ≤ m).

Определение.

Ситуацией магазинного автомата называется пара (q, γ), где q ∈ Q, γ ∈V_м* .

Определение.

Между ситуациями магазинного автомата (q, γ) и (q′, γ′) устанавливается отношение, обозначаемое символом ├ , если среди команд найдется такая, что (q, ε , z) →(q₁, γ₁), ..., (q_m, γ_m), причем γ = z β, γ′ = γ i β,

q′ = q_i для некоторого 1 ≤ i ≤ m (z ∈V_м, β ∈V_м* ).

Определение.

Говорят, что магазинный автомат переходит из состояния (q, γ) в состояние (q′, γ′) и обозначают это следующим образом:

а : (q, γ) ├ (q′, γ′).

Вводится и такое обозначение:

а₁ ... a_n : (q, γ) ├* (q′, γ′), если справедливо, что:

a_i : (q_i, γ_i) ├ (q_i+1, γ_i+1), 1 ≤ i ≤ n,

где a_i ∈ V, γ_i = γ₁, γ₂,..., γ_n+1 = γ′∈V_м* ; q_i = q₁, ..., q_n+1 = q′∈ Q.

38.Бесконтекстные (контекстно-свободные) языки.

Существует два способа определения языка, допускаемого магазинным автоматом.

Согласно первому способу считается, что входная цепочка α ∈ V* принадлежит языку L₁(M) тогда, когда после просмотра последнего символа, входящего в эту цепочку, в магазине автомата М будет находиться пустая цепочка ε.

То есть:

L₁(M) = { α | α : (q0, z0) ├* (q, ε)}, где q ∈ Q.

Согласно второму способу, считается, что входная цепочка принадлежит языку L₂(M) тогда, когда после просмотра последнего символа, входящего в эту цепочку, автомат М окажется в одном из своих заключительных состояний. Другими словами,

L₂(M) = { α | α : (q₀, z₀) ├ * (q f, γ)}, где γ∈V_м* , q_f ∈ F.

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

Доказано также, что если L(G₂) – бесконтекстный язык, порождаемый грамматикой G₂ = (V_N, V_T, P, S), являющейся формой произвольной бесконтекстной грамматики G, то существует недетерминированный магазинный автомат М, такой, что L₁(M) = L(G₂).

При этом

М = (V, Q, V_м, δ, q₀, z₀, 0),

где V = V_T; Q = {q₀}; V_м = V_N ; z₀ = S, а для каждого правила G₂ вида

А → а α, а ∈V_Т,

α ∈V_N* строится команда отображения δ:

(q₀, а, А) → (q₀, α).

Аналогично, для любого недетерминированного магазинного автомата М, допускающего язык L₁(M), можно построить бесконтекстную грамматику G такую, что L(G) = L₁(M).

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

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

39.Модель дискретного преобразователя Глушкова В. М.

Определение.

Дискретный преобразователь представляет собой абстрактный автомат А, функционирующий по соответствующим законам в дискретном времени.

Определение.

Абстрактный автомат А задается совокупностью шести объектов:

А = (Х, Y, Q, q₀, δ, λ),

где Х – конечное множество входных сигналов, называемое входным алфавитом автомата;

Y – конечное множество выходных сигналов, называемое выходным алфавитом автомата;

Q – произвольное множество, называемое множеством состояний автомата;

q₀ – элемент из множества Q, называемый начальным состоянием автомата;

δ(q, x) и λ(q, x) – две функции, задающие однозначные отображения множества пар (q, x), где q∈Q и x∈X, в множества Q и Х. Функция δ(q, x) называется функцией переходов автомата, а функция λ(q, x) – функцией выходов, либо сдвинутой функцией выходов.

Определение.

Автомат, заданный функцией выходов, называется автоматом первого рода; автомат, заданный сдвинутой функцией выходов, – автоматом второго рода.

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

В момент времени t, отличный от начального, автомат способен воспринимать входной сигнал x(t) – произвольную букву входного алфавита Х и выдавать соответствующий выходной сигнал y(t) – некоторую букву выходного алфавита Y.

Определение.

Закон функционирования абстрактного автомата первого рода задается уравнением:

где .

Определение.

Закон функционирования абстрактного автомата второго рода – уравнением:

,

где .

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

40.Понятие об абстрактном автомате и индуцируемом им отображении.

Определение.

Сущность индуцируемых абстрактным автоматом отображений заключается в реализации некоторого отображения из множества слов входного алфавита в множество слов выходного алфавита.

Определение.

Отображение реализации некоторого отображения реализуется следующим образом:

каждое слово p = x_i1, x_i2, …, x_ik входного алфавита X = (x₁, x₂, …, x_n) или, более кратко, каждое входное слово, последовательно, буква за буквой, подается на вход данного абстрактного автомата А, установленного предварительно в начальное состояние.

Возникающая таким образом конечная последовательность входных сигналов x(1) = x_i1, x(2) = x_i2, …, x(k) = x_ik на основании закона функционирования автомата вызывает появление однозначно определенной конечной последовательности s = y(1), y(2), …, y(k) выходных сигналов. Эту последовательность будем называть выходным словом, соответствующим входному слову р.

Относя, таким образом, каждому входному слову р соответствующее ему выходное слово s, мы получаем искомое отображение , а именно,

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

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