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

Недетерминированным МП-автоматом называется M=<A,Q,Г,d,q₀,Z₀,F>, где А - входной алфавит, Q - множество состояний, Г - конечное множество магазинных символов, q₀ÎQ - начальное состояние автомата, Z₀ÎГ - первый символ в магазинной памяти, FÍQ - множество заключительных состояний, d:Q´A´Г®(Q´Г)* - команды автомата.

Каждый шаг автомата задается Состоянием,Ввходным символом и Верхним символом магазина.

Операции над магазином: Втолкнуть, Вытолкнуть, Оставить без изменения.

Состояние может измениться (Состояние(S)), может не измениться.

Вход: Сдвиг или Держать.

Пример 3. КC-грамматика G=<N,T,P,S>, где N={A}, T={0,1}, S=A, P={A®01, A®0A1}

Грамматика порождает язык слов вида 0ⁿ1ⁿ, где 1<=n.

МП-автомат M=<A,Q,Г,d,q₀,Z₀,F>,

где A={0,1,^}, Q={q1,q2,Отвергнуть, Допустить }, Г={z,#}, q₀=q1, Z₀=#, F={Отвергнуть, Допустить}

Функция d:

Состояние q1		Состояние q2
М	Вход		Маг	Вход
			^					^
z	Сдвиг Состояние (q1) Втолкнуть (z)	Сдвиг Состояние (q2) Вытолкнуть	Отвергнуть		z	Отвергнуть	Сдвиг Состояние (q2) Вытолкнуть	Отвергнуть
#	Сдвиг Состояние (q1) Втолкнуть (z)	Отвергнуть	Отвергнуть		#	Отвергнуть	Отвергнуть	Допустить

Вот как работает МП-автомат:

Вход	Состояние	Магазин
000111^	q1	#
00111^	q1	#z
0111^	q1	#zz
111^	q1	#zzz
11^	q2	#zz
1^	q2	#z
^	q2	#
	Допустить

Дата добавления: 2013-12-13