Главная Обратная связь

Дисциплины:






Автомат с магазинной памятью. Допустимость по заключительному состоянию и по пустому магазину.



Автомат с магазинной памятью – это недерменированный конечный автомат с έ-переходами и одним дополнением – магазин, в котором хранится цепочка “магазинных символов”. Магазинный автомат может обозревать символ на вершине магазина и совершать переход нм основе текущего состояния, входной символ и символ на вершине магазина. Он может выполнить спонтанный переход, используя έ в качестве входного символа. За один такт автомат совершает следующие действия: 1) прочитывает и пропускает входной символ. Если в качестве входа έ, то входные символы не пропускаются. Переходит в новое состояние, которое может и не отличаться от предыдущего 3) Заменяет символ на вершине магазина некоторой цепочкой. Цепочкой может быть έ, что соответствует снятию с вершины магазина, т.е магазин не измениться. Автомат может заменить магазинный символ на один или несколько.

 

Формально МП-автомат - это семёрка объектов <Q, Σ, Г, δ, q0, Z0, F> где Q - конечное множество состояний; Σ - конечное множество символов – алфавит; Г - конечное множество символов – алфавит магазина; δ - функция переходов, которая тройке аргументов (q,a,X), q ∈Q, a ∈ Σ, X ∈ Г, ставит в соответствие множество пар (p,γ), где p - новое состояние, γ – цепочка магазинных символов, заменяющая X на вершине магазина; q0 ∈Q - начальное состояние; Z0 – начальный символ магазина.

F - Множество финальных состояний.

Допустимость. Первый способ определения МП-а допускает свой вход, прочитывая его и достигая заключительного состояния. Существует способ определения МП-а, при котором мы может определить язык допускаемый по пустому магазину, т.е множество цепочек, приводящих МП-а в начальной конфигурации к опустошению магазина. Эти два метода эквиваленты в том смысле, что для языка L найдется МП-а допускающий его по заключительному состоянию тогда и только тогда, когда для L найдется МП-а, допускающий его по пустому магазину.

По состоянию: Пусть P= <Q, Σ, Г, δ, q0, Z0, F> - МП-а, тогда L(P) – язык, допускаемый P по заключительному состоянию определяется так: {w | (q0 w, Z0 ) } |-* (q, έ, α)} для некоторого состояния q из F и произвольной магазинной цепочки α. Таким образом начиная со стартовой конфигурации с w на входе, P прочитывает w и достигает допускающего состояния. Содержимое магазина при этом не имеет значения.
По магазину: Пусть P - МП-а, тогда N(P) {N – пустой магазин} – язык, допускаемый P по пустому магазину определяется так:
N(P) = {w| (q0 w Z0) |-* (q, έ, έ)} где q – любое состояние. Таким образом N(P) представляет собой множество входов w, которые P может прочитать, одновременно опустошив магазин.





sdamzavas.net - 2019 год. Все права принадлежат их авторам! В случае нарушение авторского права, обращайтесь по форме обратной связи...