4.2. Задания

4.2.1. Построение детерминированного автомата с магазинной памятью

4.2.1.8.   Построить детерминированный магазинный автомат, распознающий цепочки из множества { 0ⁿ10ⁿ , n > 0 }.

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

δ (q₀, 0, Z)={(q₁, 0Z)}

δ (q₁, 0, 0)={(q₁, 00)}

δ (q₁, 1, 0)={(q₂, 0)}

δ (q₂, 0, 0)={(q₃, ε)}

δ (q₂, ε, Z)={(q₃, ε)}

Разбор 00100 (принадлежит языку):

(q_0, 00100, Z) ├₁ (q_1, 0100, 0Z) ├₂ (q_1, 100, 00Z) ├₃ (q_2, 00, 00Z) ├₄

(q_2, 0, 0Z) ├₄ (q_2, ε, Z) ├₅ (q_3, ε, ε).

Разбор 0100 (не принадлежит языку):

(q_0, 0100, Z) ├₁ (q_1, 100, 0Z) ├₃ (q_1, 00, 0Z) ├₄ (q_1, 0, Z) - ошибка

4.2.2. Построение детерминированного преобразователя с магазинной памятью.

4.2.2.10. Построить детерминированный преобразователь с магазинной памятью, осуществляющий перевод цепочки b_i в цепочку (b_i+1)^r, где b_i – цепочка из нулей и единиц, являющаяся бинарным представлением числа i.

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

D=({q₀, q₁, q₂, q₃, q₄}, {0, 1}, {Z, 0, 1}, {0, 1}, δ, q, Z, {q₄})

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

δ (q₀, 1, Z)=(q₁, 1Z, ε)

δ (q₁, 0, 0)=(q₁, 00, ε)

δ (q₁, 1, 0)=(q₁, 10, ε)

δ (q₁, 0, 1)=(q₁, 01, ε)

δ (q₀, 1, 1)=(q₁, 11, ε)

δ (q₁, ε, 0)=(q₂, 0, ε)

δ (q₁, ε, 1)=(q₂, 1, ε)

δ (q₂, ε, 0)=(q₃, ε, 1)

δ (q₂, ε, 1)=(q₂, ε, 0)

δ (q₂, ε, Z)=(q₄, ε, 1)

δ (q₃, ε, 0)=(q₃, ε, 0)

δ (q₃, ε, 1)=(q₃, ε, 1)

δ (q₃, ε, Z)=(q₄, ε, ε)

Разбор 101 (принадлежит языку):

5=101 → (6=110)^r=011

(q_0, 101, Z, ε) ├₂ (q_1, 01, 1Z, ε) ├₃ (q_1, 1, 01Z) ├₄ (q_1, ε, 101Z, ε) ├₈ (q_2, ε, 101Z, ε) ├₁₀ (q_2, ε, 01Z, 0) ├₉ (q_3, ε, 1Z, 01) ├₁₃ (q_3, ε, Z, 011) ├₁₄ (q_4, ε, ε, 011).

Разбор 103 (не принадлежит языку):

(q_0, 103, Z, ε) ├₂ (q_1, 03, 1Z, ε) ├₃ (q_1, 3, 01Z) - ошибка

4.2.3. Построение недетерминированного мп-автомата по кс-грамматике

4.2.3.12. T = { i, =, * }, N = { S, L, B }, R = { S  → L = B, S  → B, B  → *B, B  → L, L  → i };

Определим функции перехода для МП-автомата:

δ(q, ε, S) = {(q, L=B), (q, B)}

δ(q, ε, B) = {(q, *B), (q, L)}

δ(q, ε, L) = {(q, i)}

δ(q, i, i) ={( q, ε)}

δ(q, =, =) = {( q, ε)}

δ(q, *, *) ={( q, ε)}

4.2.4. Построение недетерминированного расширенного мп-автомата по кс-грамматике

4.2.3.8. T = { begin, end, d, p, ;}, N = { S, D, P }, R = { S → begin D ; P end, D  → d, D  → D ; d, P → p, P  → P ; p }.

Определим функции перехода для расширенного МП-автомата:

δ(q, ε, begin D ; P end) = {(q,S)}

δ(q, ε, D ; d) = {(q, D)}

δ(q, ε, d) = {(q, D)}

δ(q, ε, p) = {(q, P)}

δ(q, ε, P ; p) = {(q, P)}

δ(q, begin, ε) = {(q, begin)}

δ(q, end, ε) = {(q, end)}

δ(q, d, ε) = {(q, d)}

δ(q, p, ε) = {(q, p)}

δ(q,; , ε) = {(q, ;)}