Магазинные автоматы. Как магазинные автоматы воспринимают языки программирования

Московский Энергетический Институт

(Технический Университет).

Институт Автоматики и  Вычислительной Техники.

 

 

             

Творческая работа по Теории Автоматов

На тему :

Магазинные автоматы. Как  магазинные автоматы воспринимают языки  программирования.

 

 

 

 

 

                         

 

 

                                                           

 Выполнил студент группы А-08-09

                                                                          Купцов Вадим

 

 

Содержание.

1.Введение.

2.Автоматы.Переход от структурного и конечного автоматов  к магазинным автоматам.

3. Немного о стеках.

4. Отличия

5. Пример магазинного автомата распознающего нерегулярный язык.

6. Детерминированные и недетерминированные  автоматы.

7. Автоматное программирование

8. Необходимость магазинных автоматов

9.Описание и команды магазинного  автомата. Примеры.

10. Приложение к программе.

11. Исходный код программы.

12.Выводы.

13. Список Использованной литературы

 

 

 

 

 

 

 

 

 

 

1.Введение

В жизни сами того не подозревая мы очень часто встречаемся с  разными видами автоматов. Наиболее часто мы встречаемся с конечными автоматами. Системы синтаксического анализа и перевода текста, компьютерные игры, системы управления сложными техническими устройствами, пользовательские интерфейсы, компиляторы, также конечные автоматы применяются для разработки приложений для мобильных телефонов и при написании мобильных операционных систем. Но при создании например программ для восприятия контекстно-свободных грамматик и других приложений для работы с языком и с анализом текста, гораздо более удобно применение магазинных автоматов.

Когда мы говорим о ”магазинных”  автоматах мы должны понимать, что это автоматы с магазинной памятью. Автоматы и преобразователи с магазинной памятью играют важную роль при построении автоматно-лингвистических моделей различного назначения, связанных с использование бесконтекстных языков( контекстно-свободных) языков. В частности, такие устройства используются в большинстве работающих программ для синтаксического анализа программ для синтаксического анализа программ, написанных на различных языках программирования , которые во многих случаях можно рассматривать как без контекстные.

Для начала я хочу показать различие между знакомыми нам автоматами и магазинными.

2.Автоматы.Разница между абстрактным, конечным и магазинным автоматами.

Для начала дадим определение абстрактных  автоматов:

Абстрактный автомат - математическая абстракция, модель дискретного устройства ,имеющего один вход, один выход и в каждый момент времени находящегося в одном состоянии их множества возможных. На вход этому устройству поступают символы одного алфавита, на выходе оно выдаёт символы другого алфавита.

Это изображение абстрактного автомата.

Формально абстрактный автомат  определяется как пятерка :

A= (S, X, Y, δ, λ)

Где:

S-конечное множество состояний  автомата.

X,Y- конечные входной и выходной и выходной алфавиты из которых формируется считываемая строка и строка которую выдаёт автомат.

δ : S x X → S – Функция переходов

λ : S x X → Y – функция выходов

Функционирование автомата состоит  в порождении двух последовательностей : последовательности очередных состояний автомата и последовательности выходных символов, которые для последовательности входных символов разворачиваются в моменты дискретного времени t= 1,2,3… Моменты дискретного времени получили название тактов.

 Функционирование автомата  так же можно описать системой  соотношений,  которые описывают зависимости состояний и выходных сигналов в различные промежутки времени.

Запишем эти соотношения :

 S(t+1) = δ(s(t),x(t));

  Y(t) = λ(s(t),x(t)).

  Приведём схему работы абстрактного автомата :

Ограничение числа параметров абстрактного автомата определило такое понятие  как конечный автомат.

Конечный автомат.

Конечный автомат – абстрактный автомат без выходного потока, число возможный состояний которого конечно. Результат работы автомата определяется по его конечному состоянию.

Конечный автомат ровно как  и абстрактный можно определить пятёркой :

A=(S, X, δ, q0, F) где:

S- конечное множество состояний  автомата,

X-допустимый входной алфавит( конечное множество допустимых входных символов), из которого формируются строки считываемые автоматом;

δ- заданное отображение множества  S x X во множество P(S) подмножеств S.

δ: S x X →P(S) – также можно назвать функцией переходов.

q0- начальное состояние автомата

F- множество заключительных( или допускающих) состояний , таких что F ⊆S

Приведём схему работы автомата и опишем её:

 

Автомат начинает работу в состоянии q0, считывая по одному символу входной  строки. Считанный символ переводит  автомат в новое состояние  из S в соответствии с функцией переходов. Если по завершении считывания входного слова (цепочки символов) автомат оказывается в одном из допускающих состояний, то слово «принимается» автоматом. В этом случае говорят, что оно принадлежит языку данного автомата. В противном случае слово «отвергается».

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

Приведём общую структурную  схему конечного автомата :

Комбинационная схема строится на логических элементах, образующих функционально  полную систему, а память – на элементарных автоматах, обладающих полной системой переходов и выходов.

Sr( r изменяется 1…R) – служит для кодирования состояний набором элементов памяти.

Изменение состояния элементов  памяти происходит под действием  сигналов , поступающих на их входы. Эти сигналы формируются комбинационной схемой КС1 и называются сигналами возбуждения элементарных автоматов. На вход КС1, кроме входных сигналов, по цепи обратной связи поступают сигналы) с выходов элементов памяти автомата. Комбинационная схема КС2 служит для формирования выходных сигналов , причем в случае автомата Мили на вход этой схемы поступают входные сигналы, а в случае автомата Мура – входные сигналы не поступают.

Теперь , после того как мы описали структурный и конечный автоматы, перейдём к нашей главной задаче.

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

В теории автоматов, автомат с магазинной памятью — это конечный автомат, который использует стек для хранения состояний.

В отличие от конечных автоматов, автомат  с магазинной памятью является набором:

A=(S, X ,δ, q0, F, M, m)

 Где :

 S– конечное множество состояний автомата

X — допустимый входной алфавит, из которого формируются строки, считываемые автоматом

δ- отображение или функция перехода ( про нее подробнее ниже).

q0 ∈S — единственно допустимое начальное состояние автомата

F ⊂S — множество конечных состояний, причём допустимо F=Ø, и F=S

M— алфавит памяти (магазина)

— нулевой элемент памяти.

Память работает как стек, то есть для чтения доступен последний записанный в неё элемент. Таким образом, функция перехода является отображением

δ: S x X x M→S x M.

 То есть, по комбинации текущего состояния, входного символа и символа на вершине магазина автомат выбирает следующее состояние и, возможно, символ для записи в магазин.

 

 

Структурная схема работы магазинного  автомата :

Finite control – Конечный автомат

Stack – стэк с помощью которого реализуется память, top- вершина стека, доступный нам элемент.

Input tape – входная лента( рабочая лента).

3.Немного о стеках

Стек (stack — стопка) — структура данных, в которой доступ к элементам организован по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»). Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю.

 При работе со стеком  у  нас есть две операции 

Push-добавление (проталкивание)

Pop- удаление (выталкивание)

4.Отличия

 По сути, автомат с магазинной  памятью –несколько доработанный конечный автомат.

Мы увидели уже некоторые различия между магазинным автоматом и конечным, такие как наличие стека , условия завершения работы.

Теперь укажем еще одно отличие.

Правила перехода обычного конечного  автомата сопоставляют паре ( состояние, символ) какое-то новое состояние . Правила перехода магазинного автомата немного сложнее. Каждой тройке ( состояние, символ, стек) теперь сопоставляют пару ( состояние*, стек*). Смысл компонентов “состояние”, ”символ” и ”состояние*”, тот же ,что и раньше, при этом переходы без очередного символа считаются допустимыми . Компонент стек  определяет, какие символы должны находиться на вершине стека в данный момент. При выполнении перехода эти символы снимаются с вершины стека.

Компонент стек* правой части  правила, определяет символы , которые кладутся на вершину стека при переходе.

  5.Приведём пример автомата с магазинной памятью , распознающего нерегулярный язык.

Рассмотрим например такой язык строки которого содержат произвольное количество ,букв “А” , за которым следует столько же букв ''B''.

Приведём рисунок:

1.Алфавит у нас состоит из двух символов: А и В

2.Стартовое состояние q0

3. Допускающее состояние F.

4. Множество стековых символов содержит те же элементы, что и алфавит.

Автомат включает в себя четыре правила перехода :

q0,a,ε →A,a

A, a ,ε →A, a

A,b, a → F, ε

F,b,a  → F, ε

Где ε – эпсилон переход- переход без считывания очередного символа .