 |
|
Построение детерминированного конечного преобразователя
Определить конечный преобразователь, осуществляющий перевод последовательности составных имен (идентификаторов, разделенных символом ".") в последовательность цепочек 1n , где n – число простых идентификаторов, входящих в состав составного идентификатора. Элементы последовательности разделяются запятой, признаком конца последовательности является символ "#".
Функции переходов и выходов, таблица переходов и выходов и граф переходов и выходов детерминированного конечного преобразователя.
а – любой символ имени
d(q0, a) = {(q1, e)}
d(q1, a) = {(q1, e)}
d(q1, .) = {(q2, 1)}
d(q1, , ) = {(q3, 1)}
d(q1, #) = {(qe, 1)}
d(q2, a) = {(q1, e)}
d(q3, a) = {(q1, ,)}
| q1 |
| q0 |
| q2 |
| q3 |
| qe |
| a |
| a |
| . |
| , |
| a |
| a |
| # |
Последовательность конфигураций и выходная цепочка конечного преобразователя при переводе цепочки, принадлежащей языку.
AB.D,C,A# результат преобразования должен быть 11,1,1
(q0, AB.D,C,A#,e) ->(q1, B.D,C,A#, e)->(q1, .D,C,A#, e)->(q2, D,C,A#,1)->(q1, ,C,A#, 1)->(q3, C,A#, 11)->(q1, ,A#, 11,)->(q3, A#, 11,1)->(q1, #, 11,1,)->(qe, e, 11,1,1)
Последовательность конфигураций конечного преобразователя при переводе цепочки, не принадлежащей языку.
C.D,A.# данная цепочка не принадлежит языку.
(q0, C.D,A.#,e) -> (q1, .D,A.#,e) ->(q2, D,A.#, 1)-> (q1, ,A.#,1)-> (q3, A.#,11)-> (q1, .# ,11,)-> (q2, #, 11,1).
Построение детерминированного конечного преобразователя
Определить конечный преобразователь, осуществляющий перевод последовательности составных имен (идентификаторов, разделенных символом ".") в последовательность цепочек 1n , где n – число простых идентификаторов, входящих в состав составного идентификатора. Элементы последовательности разделяются запятой, признаком конца последовательности является символ "#".
Функции переходов и выходов, таблица переходов и выходов и граф переходов и выходов детерминированного конечного преобразователя.
а – любой символ имени
d(q0, a) = {(q1, e)}
d(q1, a) = {(q1, e)}
d(q1, .) = {(q2, 1)}
d(q1, , ) = {(q3, 1)}
d(q1, #) = {(qe, 1)}
d(q2, a) = {(q1, e)}
d(q3, a) = {(q1, ,)}
| q1 |
| q0 |
| q2 |
| q3 |
| qe |
| a |
| a |
| . |
| , |
| a |
| a |
| # |
Последовательность конфигураций и выходная цепочка конечного преобразователя при переводе цепочки, принадлежащей языку.
AB.D,C,A# результат преобразования должен быть 11,1,1
(q0, AB.D,C,A#,e) ->(q1, B.D,C,A#, e)->(q1, .D,C,A#, e)->(q2, D,C,A#,1)->(q1, ,C,A#, 1)->(q3, C,A#, 11)->(q1, ,A#, 11,)->(q3, A#, 11,1)->(q1, #, 11,1,)->(qe, e, 11,1,1)
Последовательность конфигураций конечного преобразователя при переводе цепочки, не принадлежащей языку.
C.D,A.# данная цепочка не принадлежит языку.
(q0, C.D,A.#,e) -> (q1, .D,A.#,e) ->(q2, D,A.#, 1)-> (q1, ,A.#,1)-> (q3, A.#,11)-> (q1, .# ,11,)-> (q2, #, 11,1).
Построение детерминированного автомата (распознаватель) с магазинной памятью
Формулировка задания
Построить детерминированный автомат с магазинной памятью.
Задание
4.2.1.3. Построить детерминированный магазинный автомат, распознающий цепочки в алфавите { 0,1 } с одинаковым количеством нулей и единиц.
Решение
Функции переходов, для этого автомата будут выглядеть следующим образом:
d(q0, 0, Z) = (q0, 0Z);
d(q0, 1, Z) = (q0, 1Z);
d(q0, 0, 0) = (q0, 00);
d(q0, 1, 1) = (q0, 11);
d(q0, 1, 0) = (q0, ε);
d(q0, 0, 1) = (q0, ε);
d(q0, ε, Z) = (q1, ε).
q1 – конечное состояние.
Последовательность конфигураций при разборе цепочки 110010, принадлежащей языку:
(q0, 110010, Z), (q0, 10010, 1Z), (q0, 0010, 11Z), (q0, 010, 1Z), (q0, 10, Z), (q0, 0, 1Z), (q0, ε, Z),(q1, ε, Z).
Последовательность конфигураций при разборе цепочки 1110, не принадлежащей языку:
(q0, 1110, Z), (q0, 110, 1Z), (q0, 10, 11Z), (q0, 0, 111Z), (q0, ε, 11Z). Из текущего состояния не возможно совершить переход.