Системное программное обеспечение: Основы трансляции. Карпушин А.Н - 18 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

20
Двусторонние распознаватели допускают, что считывающее устройство
может перемещаться относительно цепочки входных символов в обоих направ-
лениях: как вперед, от начала ленты к концу, так и назад, возвращаясь к уже
прочитанным символам.
По видам устройства управления распознаватели бывают детерминиро-
ванные и недетерминированные.
Распознаватель называется детерминированным в том случае, если для
каждой допустимой конфигурации распознавателя, которая возникла на неко-
тором шаге его работы, существует единственно возможная конфигурация, в
которую распознаватель перейдет на следующем шаге работы.
В противном случае распознаватель называется недетерминированным.
Недетерминированный распознаватель может иметь такую допустимую конфи-
гурацию, для которой существует некоторое конечное множество конфигура-
ций, возможных на следующем шаге работы. Достаточно иметь хотя бы одну
такую конфигурацию, чтобы распознаватель был недетерминированным.
По видам внешней памяти распознаватели бывают следующих типов:
1. распознаватели без внешней памяти;
2. распознаватели с ограниченной внешней памятью;
3. распознаватели с неограниченной внешней памятью.
У распознавателей без внешней памяти эта память полностью отсутствует.
В процессе их работы используется только конечная память устройства управ-
ления, доступ к внешней памяти не выполняется.
Для распознавателей с ограниченной внешней памятью размер внешней
памяти ограничен в зависимости от длины исходной цепочки символов. Эти
ограничения могут налагаться некоторой зависимостью объема памяти от дли-
ны цепочки – линейной, полиномиальной, экспоненциальной и т. д. Кроме того,
для таких распознавателей может быть указан способ организации внешней па-
мяти – стек, очередь, список и т. п.
Распознаватели с неограниченной внешней памятью предполагают, что
для их работы может потребоваться внешняя память неограниченного объема
(как правило, вне зависимости от длины входной цепочки). У таких распозна-
вателей предполагается память с произвольным методом доступа.
Вместе эти три составляющих позволяют организовать общую классифи-
кацию распознавателей. Например, в этой классификации возможен такой тип:
«двусторонний недетерминированный распознаватель с линейно ограниченной
стековой памятью».
Чем выше в классификации стоит распознаватель, тем сложнее создавать
алгоритм, обеспечивающий его работу. Разрабатывать двусторонние распозна-
ватели сложнее, чем односторонние, недетерминированные распознаватели по
сложности выше детерминированных, зависимость затрат на создание алгорит-
ма от типа внешней памяти также очевидна.
Классификация распознавателей по типам языков
Сложность распознавателя напрямую связана с типом языка, входные це-
почки которого может принимать (допускать) распознаватель. Доказано, что

Страницы