Магазинен автомат

Описание

Магазинен автомат (наричан още стеков автомат) е абстрактна крайна математическа машина, която работи като чете дадена дума от лента, преминава от едно състояние в друго и обработва стек.
Машината работи на крайни (дискретни) стъпки, като на всяка стъпка прочита следващата буква от лентата (незадължително), прочита най-горния символ от стека (отново незадължително) и преминава в ново състояние, евентуално записвайки символ върху стека. Математически се означава с:
М = (S, Σ, Г, s, F, δ), където:

1. S – крайно множество от състояния на машината
   
2. Σ – азбука, крайно множество от букви. Входната дума е низ от такива букви, w ∈ Σ*
   
3. Г – азбука на стека, може да се различава от Σ, но обикновено се използват същите означения, за да бъде по-интуитивна работата на машината
   
4. s ∈ S – начално състояние
   
5. F ⊆ S – множество от крайни (финални, заключителни) състояния
   
6. δ – функция на прехода, релация от вида (S, Σ ∪ {ε}, Г ∪ {ε}) x (S, Г ∪ {ε})
   

(Всяко правило в δ се чете: от състояние s при прочитане на входна буква от лентата и прочитане на най-горната буква от стека, преминаваме в състояние s', записвайки буква на стека. Символът ε е означение за празната дума и показва, че не е задължително да се чете входна буква, т.е. прочитаме празната дума. Например правило от вида (q1, ε, ε) → (q2, a) преминава от състояние q1 (без да чете нищо) в състояние q2, записвайки a на върха на стека.)

Едно приложение на стековите автомати е разпознаването кога дадена дума принадлежи на определена контекстно свободна граматика.

Допълнително

Едно предимство на стековите автомати е, че самите те могат да бъдат кодирани и записани на лента по такъв начин, че да могат да бъдат разпознати от Машина на Тюринг, която да върши същата работа, каквато би свършил и стековият автомат.

Пример

Ето един пример за представяне на стеков автомат със стандартния начин на запис:

M = {S, Σ, Г, s, F, δ}:

1. S = {1, 2, 3, 4}
2. Σ = {a, b}
3. Г = {!, a}
4. s = 1
5. F = {3}
6. δ = { (1, ε, ε) -> (2, !), (2, a, ε) -> (2, a), (2, b, a) -> (3, ε), (3, b, a) -> (3, ε), (3, a, ε) -> (4, ε), (3, b, !) -> (4, ε) }

Автоматът разпознава израз от вида a...ab...b, където броят на a е равен на броят на b. Работи на следния принцип – в началото записва символа '!' в стека, който ще ни служи да разпознаваме кога сме стигнали края на стека. След това ако прочете 'b' като първа буква или ако думата е празна, автоматът спира и не разпознава думата, защото няма такъв преход. Ако прочете 'a', записва символ 'a' в стека и остава в същото състояние (2). Ако прочете 'b', изтрива един символ 'a' от стека и преминава в състояние (3), което е и заключително. Там продължава да чете 'b' и да изпразва стека, като: ако прочете 'a', значи думата не е от търсения вид и преминава в състояние (4), което не е заключително. Ако прочете символа '!' от стека и символа 'b' от лентата, значи вече има повече b отколкото a и думата не е от търсения вид – отново преминава в състояние (4). Тъй като накрая в стека остава един символ '!', условието автоматът да разпознача думата е да е прочел цялата дума и да е в заключително състояние.

Горният пример е важен за стековите автомати, понеже показва голяма разлика между стеков автомат и краен автомат, при който разпознаването на тази дума е невъзможно.

Литература

• Р. Хантер, Проектирование и конструирование компиляторов, Москва, Финансы и статистика, 1984, ББК 32.973 6Ф7.3 Оригинал: Robin Hunter, The Design and Construction of Compilers, 1981, John Wiley & Sons Ltd