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

Содержание

Слайд 2

Определение 14.21 Автомат с магазинной памятью – это односторонний недетерминированный распознаватель.

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

Автомат с магазинной памятью – это односторонний недетерминированный распознаватель. Автомат

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

Автомат с магазинной памятью (МП-автомат) – это семерка
P = (Q, Σ, Г, δ, q0, Z0, F), где

Слайд 3

Q – конечное множество символов состояний, представляющих возможные состояния управляющего устройства;

Q – конечное множество символов состояний, представляющих возможные состояния управляющего устройства;
Σ

- конечный входной алфавит (алфавит входной ленты);
Г – конечный алфавит магазинных символов (алфавит рабочей памяти автомата);
δ - отображение множества Q × (Σ ∪ {λ}) × Г в множество конечных подмножеств множества Q × Г* (δ - функция переходов);
q0 ∈ Q – начальное состояние управляющего устройства;
z0 ∈ Г - символ, находящийся в магазине в начальный момент (начальный символ магазина);
F ⊆ Q – множество заключительных состояний управляющего устройства.
Слайд 4

В определении функции переходов запись (q′, χ) ∈ δ(q, a, Z)

В определении функции переходов запись (q′, χ) ∈ δ(q, a, Z)

будет означать:
если a ≠ λ, то МП-автомат Р, находясь в состоянии q и имея a в качестве текущего входного символа, расположенного под входной головкой, а в качестве верхнего символа магазина - символ Z, может перейти в новое состояние q′, сдвинуть входную головку на одну ячейку вправо и заменить верхний символ магазина цепочкой χ магазинных символов;
если а = λ, будем называть этот такт λ –тактом; в λ –такте текущий входной символ не принимается во внимание и входная головка не сдвигается, однако, состояние управляющего устройства и содержимое памяти могут измениться (заметим, что λ-такт может происходить и тогда, когда вся входная цепочка прочитана);
Слайд 5

Определение 14.22 если χ = λ, то верхний символ удаляется из

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

если χ = λ, то верхний символ удаляется из магазина

(магазинный список сокращается);
следующий такт невозможен, если магазин пуст

Конфигурацией МП-автомата Р называется тройка (q, ω, α) ∈ Q ×Σ*× Г*, где
q — текущее состояние управляющего устройства;

Слайд 6

ω — неиспользованная часть входной цепочки; первый символ цепочки ω находится

ω — неиспользованная часть входной цепочки; первый символ цепочки ω находится

под входной головкой; если ω=λ, то считается, что вся входная лента прочитана;
α — содержимое магазина; самый левый символ цепочки α считается верхним символом магазина; если α = λ, то магазин считается пустым.
Слайд 7

Определение 14.23 Начальной конфигурацией МП-автомата P называется конфигурация вида (q0, ω,

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

Начальной конфигурацией МП-автомата P называется конфигурация вида (q0, ω, Z0),

где ω ∈ Σ*, (т. е. УУ находится в начальном состоянии, входная лента содержит цепочку, которую нужно распознать, а в магазине есть только начальный символ Z0).
Слайд 8

Определение 14.24 Заключительной конфигурацией МП-автомата P называется конфигурация вида: (q, λ,

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

Заключительной конфигурацией МП-автомата P называется конфигурация вида: (q, λ, α),

где q ∈ F, α.∈Г*.

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

Такт работы МП-автомата Р будем представлять в виде бинарного отношения |⎯ Р, определённого на конфигурациях. Будем говорить, что между двумя конфигурациями (q, aω, Zα) и (q′, ω, χα) имеет место
(q, aω, Zα) |⎯ Р (q′, ω, χα), (**)
если (q′, χ) ∈ δ(q, a, Z), где q ∈ Q, q′ ∈ Q, a ∈ ∑ ∪ {λ}, ω ∈ ∑*, Z∈Г и α ∈ Г*, χ ∈ Г*.
Через |⎯ Р* |⎯ Р+ обозначают соответственно рефлексивное замыкание и транзитивное замыкание отношения |⎯ Р.

Слайд 9

Определение 14.26 Говорят, что цепочка ω допускается МП –автоматом P, если

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

Говорят, что цепочка ω допускается МП –автоматом P, если
(q0,

ω, Z0) |⎯ Р* (q, λ, α) для некоторого q ∈ F и α ∈ Г*.

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

Языком, определённым (или допускаемым) автоматом Р (обозначается L(P)), называют множество цепочек, допускаемых автоматом Р.

Слайд 10

Пример 14.3. Построим МП –автомат, определяющий язык L={0n1n | n≥0}. Пусть

Пример 14.3.
Построим МП –автомат, определяющий язык L={0n1n | n≥0}.
Пусть P=({q0, q1,

q2}, {0, 1}, {Z, 0}, δ, q0, Z, {q0}),
где δ(q0, 0, Z) = {(q1, 0Z)}
δ(q1, 0, 0) = {(q1, 00)}
δ(q1, 1, 0) = {(q2, λ)}
δ(q2, 1, 0) = {(q2, λ)}
δ(q2, λ, Z) = {(q0, λ)}
Работа МП –автомата Р состоит в том, что он копирует в магазине начальную часть входной цепочки, состоящую из нулей, а затем устраняет из магазина по одному нулю на каждую единицу, которую он видит на входе. Кроме того, функция переходов гарантирует, что все нули предшествуют единицам.
Слайд 11

Построим МП –автомат, определяющий язык L={wwR | w∈{0,1}+}. Пусть P=({q0, q1,

Построим МП –автомат, определяющий язык L={wwR | w∈{0,1}+}.
Пусть P=({q0, q1, q2},

{0, 1}, {Z, 0,1}, δ, q0, Z, {q2}),
где δ(q0, 0, Z) = {(q0, 0Z)}
δ(q0, 1, Z) = {(q0, 1Z)}
δ(q0, 0, 0) = {(q0, 00), (q1, λ)}
δ(q0, 0, 1) = {(q0, 01)}
δ(q0, 1, 0) = {(q0, 10)}
δ(q0, 1, 1) = {(q0, 11), (q1, λ)}
δ(q1, 0, 0) = {(q1, λ)}
δ(q1, 1, 1) = {(q1, λ)}
δ(q1, λ, Z) = {(q2, λ)}
Работа МП –автомата Р состоит в том, что он копирует в магазине начальную часть входной цепочки, состоящую из нулей и единиц, и в какой-то момент начинает вычеркивать символы из магазина, если символ, находящийся в вершине магазина, совпадает с символом входной ленты.
Слайд 12

Определение 14.28 Расширенный автомат с магазинной памятью (МП- автомат) – это

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

Расширенный автомат с магазинной памятью (МП- автомат) – это семерка
P

= (Q, Σ, Г, δ, q0, Z0, F), где
1) Q – конечное множество символов состояний, представляющих возможные состояния управляющего устройства;
2) Σ - конечный входной алфавит (алфавит входной ленты);
3) Г – конечный алфавит магазинных символов (алфавит рабочей памяти автомата);
Слайд 13

4) δ - отображение множества Q × (Σ ∪ {λ}) ×

4) δ - отображение множества Q × (Σ ∪ {λ}) ×

Г* в множество конечных подмножеств множества Q × Г* (δ - функция переходов), т.е. расширенный автомат позволяет рассматривать не один символ магазина, а цепочку символов на каждом такте работы;
5) q0 ∈ Q – начальное состояние управляющего устройства;
6) z0 ∈ Г - символ, находящийся в магазине в начальный момент (начальный символ магазина);
7) F ⊆ Q – множество заключительных состояний управляющего устройства.
Слайд 14

В определении функции переходов запись (q′, χ) ∈ δ(q, a, Z)

В определении функции переходов запись (q′, χ) ∈ δ(q, a, Z)

будет означать:
если a ≠ λ, то расширенный МП-автомат Р, находясь в состоянии q и имея a в качестве текущего входного символа, расположенного под входной головкой, а в качестве верхнего символа магазина - символ Z, может перейти в новое состояние q′, сдвинуть входную головку на одну ячейку вправо и заменить верхний символ магазина цепочкой χ магазинных символов;
если а = λ, будем называть этот такт λ –тактом; в λ –такте текущий входной символ не принимается во внимание и входная головка не сдвигается, однако, состояние управляющего устройства и содержимое памяти могут измениться (заметим, что λ-такт может происходить и тогда, когда вся входная цепочка прочитана);
Слайд 15

если χ = λ, то верхний символ удаляется из магазина (магазинный

если χ = λ, то верхний символ удаляется из магазина (магазинный

список сокращается);
если Z = λ, то содержимое магазина не анализируется.
Заметим, что в отличие от автомата с магазинной памятью, расширенный автомат с магазинной памятью может продолжить работу в случае, когда магазин пуст.
Слайд 16

Пример 14.5. Построим расширенный МП –автомат, определяющий язык L={wwR | w∈{0,1}+}.

Пример 14.5.
Построим расширенный МП –автомат, определяющий язык L={wwR | w∈{0,1}+}.
Пусть P=({q,

p}, {0, 1}, {S, Z, 0, 1}, δ, q, Z, {p}),
где δ(q, 0, λ) = {(q, 0)}
δ(q, 1, λ) = {(q, 1)}
δ(q, λ, λ) = {(q, S)}
δ(q, λ, 0S0) = {(q, S)}
δ(q, λ, 1S1) = {(q, S)}
δ(q, λ, SZ) = {(p, λ)}
Слайд 17

Определение 14.29 МП-автомат P = (Q, Σ, Г, δ, q0, Z0,

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

МП-автомат P = (Q, Σ, Г, δ, q0, Z0, F)

называется детерминированным (сокращенно ДМП-автоматом), если для каждых q ∈ Q и Z ∈ Г либо
δ(q, a, Z) содержит не более одного элемента для каждого a∈Σ и δ(q, λ, Z) = ∅, либо
δ(q, a, Z) = ∅ для всех a ∈ Σ и δ(q, λ, Z) содержит не более одного элемента.
Слайд 18

Лемма 14.5 Пусть P = (Q, Σ, Г, δ, q0, Z0,

Лемма 14.5

Пусть P = (Q, Σ, Г, δ, q0, Z0, F)

– некоторый МП-автомат. Если (q, w, A) |⎯ Рn (q', λ, λ), то (q, w, Aα) |⎯ Рn (q', λ, α) для всех A ∈ Г и α ∈ Γ*.
Доказательство.
База индукции. При n = 1 доказательство очевидно (в этом случае длина цепочи w не превосходит 1). Так как выполнено (q, w, A) |⎯ Р1 (q', λ, λ), то очевидно, что при наличии в магазине символов под символом А получим (q, w, Aα) |⎯ Р1 (q', λ, α).
Шаг индукции. Допустим, что утверждение леммы верно для всех n, таких, что n' > n ≥1. Покажем, что если выполнено (q, w, A) |⎯ Рn' (q', λ, λ), то (q, w, Aα) |⎯ Р n' (q', λ, α).
Слайд 19

Так как выполнено (q, w, A) |⎯ Рn' (q', λ, λ),

Так как выполнено (q, w, A) |⎯ Рn' (q', λ, λ),

то соответствующая последовательность тактов должна иметь вид:
(q, w, A) |⎯ (q1, w1, X1,X2,…,Xk )
|⎯ n1 (q2, w2, X2,…,Xk )
|⎯ n2 (q3, w3, X3,…,Xk )
…
|⎯ nk-1 (qk, wk, Xk )
|⎯ nk (q', λ, λ),
причем все ni < n'.
Слайд 20

Тогда для любых α возможна последовательность (q, w, Aα) |⎯ (q1,

Тогда для любых α возможна последовательность
(q, w, Aα) |⎯ (q1,

w1, X1,X2,…,Xkα )
|⎯ n1 (q2, w2, X2,…,Xkα )
|⎯ n2 (q3, w3, X3,…,Xkα )
…
|⎯ nk-1 (qk, wk, Xkα )
|⎯ nk (q', λ, α),
т.е. выполнено (q, w, Aα) |⎯ Р n' (q', λ, α). Лемма доказана.
Слайд 21

Определение 14.30 Пусть P = (Q, Σ, Г, δ, q0, Z0,

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

Пусть P = (Q, Σ, Г, δ, q0, Z0, F)

– некоторый МП-автомат или расширенный МП-автомат. Будем говорить, что P допускает цепочку w ∈Σ* опустошением магазина, если (q, w, Z0) |⎯Р* (q', λ, λ) для некоторого q ∈ Q.
Обозначим Lλ(P) – множество цепочек, допускаемых автоматом P опустошением магазина.
Слайд 22

Лемма 14.6 Пусть L = L(P) для некоторого МП-автомата P =

Лемма 14.6

Пусть L = L(P) для некоторого МП-автомата P = (Q,

Σ, Г, δ, q0, Z0, F). Тогда можно построить такой МП-автомат P', что Lλ(P') = L.
Доказательство.
Построим МП-автомат P' = (Q ∪ {qλ, q'}, Σ, Г ∪ {Z'}, δ', q', Z',∅). Определим функцию переходов следующим образом:
1. если (r,γ) ∈ δ(q, a, z), то (r,γ) ∈ δ'(q, a, z) для любых q ∈ Q, a∈Σ ∪ {λ}, z∈Г;
2. δ'(q', λ, Z') = {(q0, Z0Z')}, т.е. на первом такте автомат P' записывает в магазин Z0Z' и переходит в состояние q0 – начальное для автомата P;
Слайд 23

3. для любых q ∈ F, z ∈ Г ∪ {Z'}

3. для любых q ∈ F, z ∈ Г ∪ {Z'}

элемент (qλ, λ) ∈ δ'(q, λ, z);
4. δ'(qλ, λ, z) = {(qλ, λ)} для всех z ∈ Г ∪ {Z'}.
Очевидно, что
(q', w, Z') |⎯Р' (q0, w, Z0Z') пункт (2) определения δ'
|⎯Р'n (q, λ, Y1Y2…Yr) пункт (1) определения δ'
|⎯Р' (qλ, λ, Y1Y2…Yr) пункт (3) определения δ'
|⎯Р'r-1 (qλ, λ, λ) пункт (4) определения δ'
где Yr = Z' тогда и только тогда, когда
(q0, w, Z0) |⎯Р'n (q, λ, Y1Y2…Yr-1) для q ∈ F и Y1Y2…Yr-1 ∈ Г*. Следовательно, Lλ(P') = L.
Слайд 24

Лемма 14.7 Пусть P = (Q, Σ, Г, δ, q0, Z0,

Лемма 14.7

Пусть P = (Q, Σ, Г, δ, q0, Z0, ∅)

– МП- автомат. Можно построить такой МП-автомат P', что L(P') = Lλ(P).

Лемма 14.7

Пусть G = (N, Σ, P, S) – КС-грамматика. По грамматике G можно построить такой МП-автомат R, что Lλ(R) = L(G).
Доказательство. Построим R так, чтобы он моделировал все левые выводы в G. Верхушка магазина слева.
Пусть R = ({q}, Σ, Σ ∪ N, δ, q, S, ∅), где функция переходов δ определяется следующим образом:

Слайд 25

1. если правило вида A → α ∈ P, то (q,

1. если правило вида A → α ∈ P, то (q,

α) ∈ δ(q, λ, A);
2. для всех a ∈ Σ построим δ(q, a, a) = {(q, λ)}.
Докажем, что A ⇒ m w, где w ∈ Σ* ⇔ (q, w, A) |⎯n (q, λ, λ) для некоторых m ≥ 1 и n≥ 1.
Необходимость. Пусть имеет место A ⇒ m w при некотором m≥ 1. Покажем (индукцией по m), что тогда существует n≥ 1 такое, что выполнено (q,w, A) |⎯n (q, λ, λ).
База индукции. Если m = 1, A ⇒ 1 w и w = a1a2…ak ∈ Σ*, т.е. k ≥ 0, то правило A → w ∈ P и
(q, a1a2…ak, A) |⎯ (q, a1a2…ak, a1a2…ak) пункт (1) определения δ
|⎯k (q, λ, λ) пункт (2) определения δ, т.е. n = ⏐w⏐+1 = k+1.
Слайд 26

Предположим, что при всех m', таких, что 1 Докажем справедливость утверждения

Предположим, что при всех m', таких, что 1 < m' <

m, если A ⇒ m w, то существует n ≥ 1 такое, что выполнено (q,w, A) |⎯n (q, λ, λ).
Докажем справедливость утверждения при m. Так как A ⇒ m w, то первый шаг вывода имеет вид A ⇒ X1X2… X k, причем правило A → X1X2… X k∈ P и для всех i, 1 ≤i≤k имеет место Xi ⇒mi xi, где mi < m. Но тогда по предположению индукции (q, xi, Xi)|⎯ni (q, λ, λ), причем, в случае, когда Xi = xi ∈ Σ имеет место (q,xi,xi)|⎯ (q,λ, λ), т.е. ni = 1 . Следовательно, если A ⇒ m w, то (q, w, A) |⎯ (q, w, X1X2… Xk) |⎯n1 (q, w, X2… Xk) |⎯n2 …|⎯nk (q,λ,λ).
Достаточность. Пусть имеет место (q, w, A) |⎯n (q, λ, λ) при некотором n≥ 1. Покажем (индукцией по n), что тогда существует m ≥ 1 такое, что выполнено A⇒mw.
Слайд 27

База индукции. Если n =1 и (q, w, A) |⎯1 (q,

База индукции. Если n =1 и (q, w, A) |⎯1 (q,

λ, λ), то w = λ и правило A→λ∈P (см. определение функции переходов), т.е. A⇒1w.
Предположим, что утверждение верно при всех n', таких, что n'Первый шаг, сделанный автоматом, должен иметь вид (q, w, A) |⎯ (q, w, X1X2… Xk), причем правило A → X1X2… Xk∈ P. Пусть w = x1x2… xk, где xk ∈ Σ* и (q, xi, Xi) |⎯ni (q, λ, λ), причем ni < n, но тогда по предположению Xi ⇒mi xi, причем mi = 0, если Xi ∈ Σ. Таким образом, имеет место вывод цепочки w в грамматике G:
Слайд 28

A ⇒ X1X2… Xk ⇒* x1X2… Xk ⇒* x1x2X3… Xk ⇒*

A ⇒ X1X2… Xk
⇒* x1X2… Xk
⇒* x1x2X3… Xk
⇒* x1x2x3… xk

= w
Из условия леммы в частности следует, что S ⇒+ w ⇔ (q, w, S) |⎯+ (q, λ, λ), следовательно Lλ(R) = L(G).
Слайд 29

Пример 14.6. Построим МП –автомат P, для которого L(P) = L(G),

Пример 14.6.
Построим МП –автомат P, для которого L(P) = L(G), где

G – КС-грамматика примера 7.5, определяющая арифметические выражения.
Пусть P=({q}, Σ, Г, δ, q, E, ∅), где Σ = {a, +, *, (, )}
где δ(q, λ, E) = {(q, E+T), (q, E)}
δ(q, λ, T) = {(q, T*F), (q, T)}
δ(q, λ, F) = {(q, (E)), (q, a)}
δ(q, b, b) = {(q, λ)} для всех b ∈ Σ.
Слайд 30

Определение 14.31 Пусть G = (N, Σ, P, S) – КС-грамматика

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

Пусть G = (N, Σ, P, S) – КС-грамматика и

S ⇒r* αAw ⇒r αβw ⇒r*xw – правый вывод в G. Будем говорить, что правовыводимую цепочку αβw можно свернуть слева (или что она левосвертывается) к правовыводимой цепочке αAw с помощью правила A → β. Вхождение цепочки β в цепочку αβw назовем основой цепочки αβw.
Основа правовыводимой цепочки – это любая ее подцепочка, которая является правой частью какого–либо правила, причем после ее замены левой частью правила получается также правовыводимая цепочка.
Слайд 31

Лемма 14.9 Пусть G = (N, Σ, P, S) – КС-грамматика.

Лемма 14.9

Пусть G = (N, Σ, P, S) – КС-грамматика. По

грамматике G можно построить такой расширенный МП-автомат R, что L(R) = L(G).
Доказательство. Пусть R = ({q, r}, Σ, Σ ∪ N ∪ {#}, δ, q, #, {r}) – расширенный МП–автомат (верхушка магазина располагается справа), в котором функция переходов δ определяется следующим образом:
(1) для всех a ∈ Σ определим δ(q, a, λ) ={(q, a)} (выполняется перенос входного символа в магазин);
(2) если правило A → α ∈ P, то (q, A) ∈ δ(q, λ, α) (выполняется свертка, т.е. основа заменяется нетерминальным символом грамматики);
(3) δ(q, λ, #S) = {(r, λ)}.
Слайд 32

Докажем, что справедливо L(G) = L(R). 1. Докажем вначале справедливость L(G)

Докажем, что справедливо L(G) = L(R).
1. Докажем вначале справедливость L(G) ⊆

L(R), т.е. покажем, что если w = xy ∈ L(G), то w ∈ L(R). Для этого индукцией по n докажем, что
(*) если имеет место S ⇒r* αAy ⇒rn xy, то также (q, ху, #) |⎯m (q, y, #αA)
Базис. При n = 1 имеем αAy ⇒r1 xy. В этом случае xy = αβy и правило А → β ∈ Р. Тогда имеет место (q, ху, #) |⎯* (q, y, #αβ)|⎯ 1(q, y, #αA) (т.е. выполняем перенос входных символов до тех пор, пока в магазине не появится основа β, а затем заменяем основу нетерминальным символом A).
Предположим, что (*) верно для всех значений n' < n.
Докажем, что (*) верно для n. Вывод αAy ⇒rn xy можно представить в виде αAy ⇒r αβy ⇒rn–1 xy.
Слайд 33

Допустим, что цепочка αβ состоит только из терминалов. Тогда αβ=х и

Допустим, что цепочка αβ состоит только из терминалов. Тогда αβ=х и

(q,ху, #) |⎯* (q, у, #αβ) |⎯ (q, y, # αA).
Если αβ ∉ Σ*, т.е. αβ содержит нетерминальные символы, то можно представить αβ = γBz, где В—самый правый нетерминал. По (*) из S ⇒r* γBzy ⇒rn–1 xy следует (q, ху, #)|⎯* (q, zy, #γB). Кроме того, (q, zy, #γB) |⎯* (q, у, #γBz) |⎯ (q, у, #αA) – тоже возможная последовательность тактов (согласно предположения индукции).
Следовательно, (*) верно для всех n. Так как (q, λ, #S) |⎯ (r, λ, λ), то L(G)⊆ L(R).
Слайд 34

2. Теперь докажем обратное включение L(R) ⊆ L(G), т.е. покажем, что

2. Теперь докажем обратное включение L(R) ⊆ L(G), т.е. покажем, что

если w = xy ∈ L(R), то w ∈ L(G). Для этого индукцией по n покажем, что
(**) если имеет место (q, xy, #) |⎯n (q, y, #αA), то выполнено αАу ⇒* ху
Базис. При n = 1 имеем (q, xy, #) |⎯1 (q, y, #αA). В этом случае xy = αβy и правило А → β ∈ Р, тогда αАу ⇒1 ху = αβy.
Предположим, что (**) верно для всех n < m.
Докажем, что (**) верно для m, т.е. покажем, что если имеет место (q,xy,#)|⎯m (q, y, #αA), то выполнено αАу ⇒* ху
Если верхний символ магазина автомата R нетерминальный, то последний такт был сделан по правилу (2) определения функции δ. Поэтому можно записать
Слайд 35

(q, ху, #) |⎯m–1 (q, y, #αβ) |⎯ (q, y, #

(q, ху, #) |⎯m–1 (q, y, #αβ) |⎯ (q, y, #

αA), где правило А → β ∈ Р.
Если цепочка αβ содержит нетерминал, то по предположению индукции αβy ⇒* ху. Отсюда αAу ⇒ αβy ⇒* ху, что и утверждалось.
В качестве частного случая утверждения (**) получаем, что если выполнено (q, w, #)|⎯* (q, λ, #S), то также S ⇒* w. Так как R допускает w только тогда, когда (q, w, #) |⎯* (q, λ, #S) |⎯ (r•, λ, λ), то отсюда следует, что L(R) ⊆ L (G). Таким образом, L(R) = L(G)).
Заметим, что сразу после свертки правовыводимая цепочка вида αAx представлена в R так, что αА находится в магазине, а x занимает непрочитанную часть входной ленты. После этого R может продолжать переносить символы цепочки х в магазин до тех пор пока в его верхней части не образуется основа. Тогда R может сделать следующую свертку. Синтаксический анализатор этого типа называют „восходящим анализом" („анализом снизу вверх").
Слайд 36

Пример 14.7. Построим восходящий анализатор R для грамматики G примера 7.5.

Пример 14.7. Построим восходящий анализатор R для грамматики G примера 7.5.

Пусть R – расширенный МП-автомат R = ({q, r}, Σ, Г, δ, q, #, {r}), где Σ = {a, +, *, (, )}, а функция переходов δ определяется так:
δ(q, b, λ) = {(q, b)} для всех b ∈ Σ;
δ(q, λ, E+T) = {(q, E)}
δ(q, λ, T) = {(q, E)}
δ(q, λ, T * F) = {(q, T)}
δ(q, λ, F) = {(q, T)}
δ(q, λ, (E)) = {(q, F)}
δ(q, λ, a) = {(q, F)}
δ(q, λ, #E) = {(r, λ)}
- Предыдущая
Основы компьютерной графики языка Java. (Занятие 5)
Следующая -
Безопасность при пользовании банковской картой

Похожие презентации

Владимир Вольфович Жириновский
Прощание С Букварем - презентация для начальной школы
Любка Марина Іванівна
ФОРМИРОВАНИЕ УЧЕТНОЙ ПОЛИТИКИ ОРГАНИЗАЦИИ 1. Понятие и требования, предъявляемые к формированию учетной политики. 2. Алгорит
Презентация Либерализация экономики
Система права и система законодательства
Тема: «Русская изба XVII века (Архангельская область)»
Художественная культура XVIII века. Театр
Вороний день ( Вурна хатл ) - праздник встречи весны у народов Севера
Ислам діні
Разновидности и особенности полупроводниковых диодов
Монипуляторы
Значення кожного з семи тижнів до Великодня
Трубопроводы и трубопроводная арматура на нефтебазе, НПС
Марксизм в западной Философии
Самоорганизация сложных природных систем
Устройство надводного корабля
РАННЕЕ КОГНИТИВНОЕ РАЗВИТИЕ
Понятие и виды профессиональной этики (сравнительная характеристика административной и деловой этики)
Иммобилайзеры SHINCHANG
Выполнила: студентка 4 курса группы «Б» Игнатюк Екатерина Александровна Преподаватель: Минаева Римма Владимировна
Презентация "Основы микробиологии" - скачать презентации по Экономике
C++ для ЕГЭ
Мировые воины XX века: причины и последствия
ПЯВУ. Основы программирования. Лекция 3. Понятие цикла. Оператор while. Представление целых чисел в компьютере
Т.3 Полицейские органы в системе МВД Российской империи в условиях феодально-бюрократического режима
7. Хранение информационных объектов
Грамматика және грамматикалық бірліктер
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть