 |
|
Построение детерминированного автомата (распознаватель) с магазинной памятью
Формулировка задания
Построить детерминированный магазинный автомат, распознающий цепочки из множества { 0n1n , n > 0 } È { 1n0n , n > 0 }.
P= <{q0,q1,q2,q3,q4,q5,qe},{1,0},{1,0,Z},d ,Z, q0, qe>
Функции переходов:
d(q0,1,Z)=(q1,1Z)
d(q0,0,Z)=(q2,0Z)
d(q1,1,1)=(q1,11)
d(q1,0,1)=(q3,ε)
d(q2,0,0)=(q2,00)
d(q2,1,0)=(q4, ε)
d(q3,0,1)=(q3,ε)
d(q4,1,0)=(q4,ε)
d(q3, ε ,Z)=(qe,ε)
d(q4, ε,Z)=(qe,ε)
Последовательность конфигураций при разборе цепочки 111000, принадлежащей языку .
(q0, 111000, Z)├ (q1, 11000, 1Z) ├ (q1, 1000, 11Z) ├ (q1, 000, 111Z) ├ (q3, 00, 11Z) ├ (q3, 0, 1Z) ├ (q3, ε, Z) ├ (qe, ε, ε).
Последовательность конфигураций при разборе цепочки 00111, не принадлежащей языку .
(q0,00111,Z) ├ (q2,0111,0Z) ├ (q2,111,00Z) ├ (q4,11,0Z )├ (q4,1,Z)
Из данного состояния невозможно совершить переход.
Построение детерминированного автомата (распознаватель) с магазинной памятью
Формулировка задания
Построить детерминированный магазинный автомат, распознающий цепочки из множества { 0n1n , n > 0 } È { 1n0n , n > 0 }.
P= <{q0,q1,q2,q3,q4,q5,qe},{1,0},{1,0,Z},d ,Z, q0, qe>
Функции переходов:
d(q0,1,Z)=(q1,1Z)
d(q0,0,Z)=(q2,0Z)
d(q1,1,1)=(q1,11)
d(q1,0,1)=(q3,ε)
d(q2,0,0)=(q2,00)
d(q2,1,0)=(q4, ε)
d(q3,0,1)=(q3,ε)
d(q4,1,0)=(q4,ε)
d(q3, ε ,Z)=(qe,ε)
d(q4, ε,Z)=(qe,ε)
Последовательность конфигураций при разборе цепочки 111000, принадлежащей языку .
(q0, 111000, Z)├ (q1, 11000, 1Z) ├ (q1, 1000, 11Z) ├ (q1, 000, 111Z) ├ (q3, 00, 11Z) ├ (q3, 0, 1Z) ├ (q3, ε, Z) ├ (qe, ε, ε).
Последовательность конфигураций при разборе цепочки 00111, не принадлежащей языку .
(q0,00111,Z) ├ (q2,0111,0Z) ├ (q2,111,00Z) ├ (q4,11,0Z )├ (q4,1,Z)
Из данного состояния невозможно совершить переход.
Построение детерминированного преобразователя с магазинной памятью.
Формулировка задания
Построить детерминированный преобразователь с магазинной памятью.
Задание
4.2.2.4 Построить детерминированный преобразователь с магазинной памятью, осуществляющий перевод произвольной цепочки из множества { 0n1n 0m1m..., где n, m,...> 0 } в цепочку вида 1n+m+¼ .
Решение
Определим детерминированный преобразователь с магазинной памятью следующим образом:
P= <{q0,q1 },{1,0},{0, Z},d ,Z, q0, q1>
Функции переходов, для этого автомата будут выглядеть следующим образом:
d(q0, 0 , Z) = (q0, 0Z, ε);
d(q0, 0, 0) = (q0, 00, ε);
d(q0, 1, 0) = (q0, ε, 1);
d(q0, ε, Z) = (q1, ε, ε)
Преобразование цепочки 0001110011010011, принадлежащей языку:
(q0, 0001110011010011, Z), (q0, 001110011010011, 0Z), (q0, 01110011010011, 0Z),
(q0, 1110011010011, 000Z), (q0, 110011010011, 00Z), (q0, 10011010011, 0Z), (q0, 0011010011, Z),
(q0, 011010011, 0Z), (q0, 11010011, 00Z), (q0, 1010011, 0Z), (q0, 010011, Z), (q0, 10011, 0Z),
(q0, 0011, Z), (q0, 011, 0Z), (q0, 11, 00Z), (q0, 1, 0Z), (q1, ε, Z).
Преобразование цепочки 01001, не принадлежащей языку:
(q0, 01001, Z), (q0, 1001, 0Z), (q0, 001, Z), (q0, 01, 0Z), (q0, 1, 00Z), (q0, ε, 0Z). Из текущей конфигурации невозможно совершить переход.
Построение детерминированного преобразователя с магазинной памятью.
Формулировка задания
Построить детерминированный преобразователь с магазинной памятью, осуществляющий перевод произвольной цепочки из множества {13n+20n , n ≥ 0} в цепочку вида 1n0n.
P= <{q0,q1,q2,q4,q5, q6,q7 },{1,0},{1,0}{1,0,Z},d ,Z, q0, q7>
d(q0,1,Z)=(q1,Z, ε)
d(q1,1,Z)=(q2,Z, ε)
d(q2,ε,Z)=(q7, ε, ε)
d(q2,1,Z)=(q4,1Z, ε)
d(q2,1,1)=(q4,11, ε)
d(q2,0,1)=(q6, ε, 0)
d(q4,1,Z)=(q5,Z, ε)
d(q4,1,1)=(q5,1, ε)
d(q5,1,Z)=(q2,1Z, 1)
d(q5,1,1)=(q2,11, 1)
d(q6, 0, 1)=(q6, ε, 0)
d(q6, ε, Z)=(q7, ε, ε)
Преобразование цепочки 1111111100, принадлежащей языку.
(q0, 1111111100,Z, ε) ├ (q1, 111111100, Z, ε) ├ (q2, 11111100, Z, ε) ├ (q4, 1111100, Z, ε) ├ (q5, 111100, Z, ε) ├ (q2, 11100,1Z, 1) ├ (q4, 1100,1Z,1) ├ (q5, 100,1Z,1) ├ (q2, 00, 11Z, 11) ├ (q6, 0 ,1Z, 110) ├ (q6, ε, Z, 1100) ├ (q7, ε, ε, 1100)
Преобразование цепочки 1100, не принадлежащей языку.
(q0, 1100, Z, ε) ├ (q1, 100, Z, ε) ├ (q2, 00, Z, ε). Из текущей конфигурации невозможно совершить переход
Построение детерминированного преобразователя с магазинной памятью.
Формулировка задания
Построить детерминированный преобразователь с магазинной памятью, осуществляющий перевод произвольной цепочки из множества {13n+20n , n ≥ 0} в цепочку вида 1n0n.
P= <{q0,q1,q2,q4,q5, q6,q7 },{1,0},{1,0}{1,0,Z},d ,Z, q0, q7>
d(q0,1,Z)=(q1,Z, ε)
d(q1,1,Z)=(q2,Z, ε)
d(q2,ε,Z)=(q7, ε, ε)
d(q2,1,Z)=(q4,1Z, ε)
d(q2,1,1)=(q4,11, ε)
d(q2,0,1)=(q6, ε, 0)
d(q4,1,Z)=(q5,Z, ε)
d(q4,1,1)=(q5,1, ε)
d(q5,1,Z)=(q2,1Z, 1)
d(q5,1,1)=(q2,11, 1)
d(q6, 0, 1)=(q6, ε, 0)
d(q6, ε, Z)=(q7, ε, ε)
Преобразование цепочки 1111111100, принадлежащей языку.
(q0, 1111111100,Z, ε) ├ (q1, 111111100, Z, ε) ├ (q2, 11111100, Z, ε) ├ (q4, 1111100, Z, ε) ├ (q5, 111100, Z, ε) ├ (q2, 11100,1Z, 1) ├ (q4, 1100,1Z,1) ├ (q5, 100,1Z,1) ├ (q2, 00, 11Z, 11) ├ (q6, 0 ,1Z, 110) ├ (q6, ε, Z, 1100) ├ (q7, ε, ε, 1100)
Преобразование цепочки 1100, не принадлежащей языку.
(q0, 1100, Z, ε) ├ (q1, 100, Z, ε) ├ (q2, 00, Z, ε). Из текущей конфигурации невозможно совершить переход.