spoPresentation2

Синтаксические диаграммы

узловая точка. Обозначается точкой или закрашенным кружком

точка выхода. Никак не обозначается, в нее просто входит выходная дуга графа

Каждая диаграмма имеет только одну точку входа и одну точку выхода. Вершин остальных типов может быть сколько угодно.

Вершины соединяются направленными дугами. Из входной точки дуги только выходят, в выходную – только входят

51

Синтаксические диаграммы

Остальные вершины должны иметь как минимум один вход и один выход

Compare

Double

Double =

First

!

=

First

First <

>

52

Распознаватели

Распознаватель – это специальный автомат, который позволяет определить принадлежность цепочки символов некоторому языку

а0 а1 а2 … аn

УУ П

53

Распознаватели

Поведение распознавателя отслеживается по его конфигурациям

Конфигурация определяется

состоянием УУ

содержимым входной ленты и положением головки

содержимым рабочей памяти

54

Распознаватели

Конфигурация называется начальной, если УУ находится в заданном начальном состоянии, входная головка установлена на первый символ последовательности и рабочая память имеет заранее установленное начальное содержимое

Конфигурация заключительная, если УУ находится в одном из заданных заключительных состояний, а входная головка находится за концом исходной цепочки

55

Распознаватели

Распознаватель допускает входную цепочку Z, если, находясь в начальной конфигурации

и получив на вход эту цепочку, он может проделать последовательность шагов, заканчивающуюся одной из его заключительных конфигураций

Язык, определяемый распознавателем – это множество всех цепочек, которые допускает распознаватель

56

Распознаватели

По типу считывающего устройства

односторонние и двусторонние

По направлению считывания

левосторонние (слева направо) и правосторонние

57

Распознаватели

По виду УУ

Детерминированные (для каждой допустимой конфигурации, которая может возникнуть на некотором шаге, существует единственно возможная конфигурация, в которую распознаватель перейдет на следующем шаге)

Недетерминированные (существует несколько допустимых конфигураций)

58

Распознаватели

По виду рабочей памяти

без внешней памяти

с ограниченной внешней памятью (объем зависит от длины входной цепочки символов)

с неограниченной внешней памятью

59

Распознаватели

Для случая преобразования одного языка в другой распознаватель дополнительно использует выходную ленту, на которую пишет результат

Такой распознаватель называется преобразователем

Если входная строка переводит преобразователь из начальной конфигурации в заключительную, строка на выходной ленте считается переводом входной строки

60