Читайте также:
|
Структуру магазинного преобразователя составляют:
1. конечный управляющий автомат
2. три магазина – входной, внутренний и выходной.
3. три канала, связывающие управляющий автомат с магазинами.
Входной магазин работает только в режиме чтения, выходной –только в режиме записи, а внутренний магазин может работать в двух режимах.
Множество состояний Q управляющего автомата разбито на два подмножества Q1 и Q2. Если состояние управляющего автомата принадлежит к подмножеству Q1, то происходит считывание из входного и внутреннего магазина.
Если же состояние управляющего автомата относится к подмножеству Q2, то происходит считывание только из внутреннего магазина, в этот же момент автомат переходит в новое состояние и записывает во внутренний и входной магазины некоторые слова.
Примечание. Акцептор (распознающий МП – автомат) не имеет выходной ленты, а порождающий МП – автомат не имеет входной ленты.
Пусть A,Z,B – алфавит соответственно входного, внутреннего и выходного магазинов, не содержащие пустых букв, тогда функционирование МП – преобразователя можно представить выражениями:
Значения этих функций указывают новое состояние и слова, которые записываются во внутренний и выходной магазины. При этом действия МП – автоматов не определены в случае пустого входного или внутреннего магазинов.
в) Формальное определение МП – акцептора.
В общем виде, инициальный распознаватель с входной и внутренней лентами определяется как кортеж семи компонент 
, где
А – алфавит входных (терминальных) символов;
Q – множество состояний;
Z – конечный алфавит, состоящий из терминальных и нетерминальных символов(при этом 
Δ – функция переходов МП – автоматов
, здесь 
- булеан, т.е. множество подмножеств 
;
q0 – начальное состояние акцептора, 
;
z0 - маркер внутреннего стека, 
;
F – множество конечных состояний, 
.
Дата добавления: 2015-12-01; просмотров: 33 | Нарушение авторских прав