На головну

Детерміновані автомати з магазинною пам'яттю

  1.  А також для більшості випадкових процесів з кінцевої лінійної статистичної пам'яттю виконується
  2.  Автомати для продажу рідких і штучних товарів
  3.  Буферизація обміну даними між зовнішньою і основною пам'яттю
  4.  Детерміновані і квазідетермінірованние процеси, їх опис в рамках теорії випадкових процесів, вираження для n-мірних щільності ймовірності.
  5.  Детерміновані мережі черг
  6.  Історичні типи журналістики і детерміновані ними професійні компетенції

(МП-автомати)

Є «проміжна» математична модель між автоматами і контекстно-вільними граматиками - автомат з магазинної пам'яттю. (МП-автомат).

Існує досить поширена завдання - завдання визначення парності дужок. Однак її не можна уявити автоматною граматикою.

Відповідна граматика може виглядати наступним чином:

S® (S)

S®SS

S®e

МП-автомат складається з вхідних стрічки, в осередках якої записується анализируемая рядок (+-кінець рядка), пристрої керування й розбитого на осередки магазину (стека). N ??- символ порожнього магазину. Пристрій управління автомата може). "Пам'ятати" стан (S1 ...).

Потрібно розпізнати: (() ())


(() ()) +

       
 
   
 


N

Роботу автомата можна описати програмою.

 S1 X N
(  ? X ®  ? X ®
) ® ?
+ ? +

Тут і далі використовуються позначення:

?a - помістити рядок a в вершину магазину.

 a - замінити верхній символ магазину на рядок a.

a - прибрати символ з вершини магазину.

® - зрушити на крок вправо по вхідному рядку.

 > <- Стояти на місці.

? - відкинути.

+ - Прийняти.

S - State - стан МП-автомата (на кожне стан своя таблиця, тут одне стан S1).

N ??[S1] (() ()) +

xN [S1] (() ()) +

xxN [S1] (() ()) +

xN [S1] (() ()) +

xxN [S1] (() ()) +

xN [S1] (() ()) +

N ??[S1] (() ()) +

Завдання розпізнавання вкладених дужок "типу матрьошка" складніше і для її розпізнавання потрібно МП-автомат з двома станами:

((()))

S2 X N
( ? ?
) S2 ® ?
+ ? +
S1 X N
( S1? X ® S1? X ®
) S2 ® ?
+ ? +

При зустрічі першої закриває дужки МП автомат змінює стан S1 на стан S2.

 




 Нормальні алгорифм Маркова |  Нормальна схема преобразуемое |  рекурсивні функції |  L-числення |  Поняття формальної граматики |  дерева виведення |  Класифікація мов по Хомського |  розпізнають автомати |  поняття транслятора |  детермінованого |

© um.co.ua - учбові матеріали та реферати