Конфигурация МП (до 15 минут)

Конфигурация МП – автомата описывается тройкой , где q – текущее состояние акцептора, α – цепочка непрочитанных терминальных символов на входной ленте, ώ - цепочка символов во внутреннем стеке. Такт работы перехода МП – автомата описывается в виде , если , в приведенном выражении .

Начальная конфигурация МП – автомата определяется, как , а множество его конечных конфигураций МП – автомат допускает цепочку α символов входной ленты, если, находясь в начальной конфигурации, он может перейти в одну из конечных конфигураций . В противном случае входная цепочка не принимается.

Пример. Последовательность конфигураций МП – автомата принимающего арифметическое выражение , согласно продукциям , представим таблицей:

КОНФИГУРАЦИИ.	Дерево вывода
Состояние q	Входное слово α	Содержимое стека
q1=q0	a´(b+c)	z0	´
q2	a´(b+c)	Jz0
q2	a´(b+c)	Tz0
q2	a´(b+c)	T´Fz0
q2	a´(b+c)	F´Fz0
q2	a´(b+c)	a´Fz0
q2	´(b+c)	´Fz0
q2	(b+c)	Fz0
q2	(b+c)	(J)z0
q2	b+c)	J)z0
q2	b+c)	J+T)z0
q2	b+c)	T+T)z0
q2	b+c)	F+T)z0
q2	b+c)	b+T)z0
q2	+c)	+T)z0
q2	c)	T)z0
q2	c)	F)z0
q2	c)	c)z0
q2	)	)z0
q2	а0	z0
q3=q2	а0	e

Пояснение. Рассматриваемый недетерминированный МП – автомат эмулирует вывод с помощью операций со стеком следующим образом: при каждом переходе автомата из стека извлекается символ, определяющий следующее действие автомата. Если извлеченный символ нетерминальный, то вместо него в стек заключится правая часть продукции, соответствующей этому символу. Если извлеченный из†стека символ – терминальный, то он используется в качестве входного символа и, следовательно, определяет переход автомата.

Теорема. Классы КС – языков и языков, допускаемых МП – автоматами, совпадают.

(доказательство на дом)

Лекция №23.

Дата добавления: 2015-12-01