Робототехника.Фу, Ли, Гонсалес (962794), страница 80

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 80)

сс может быть любой цепочкой, состоящей из констант и переменных за исключением пустой цепочки. Пример. Смысл рассмотрен- l ных понятий поясним на следующем примере. Предположим, что объект, показанныи на рис. 8.55, а, представляется своим скелетом. Для описания структуры подоб- Я ных скелетов введем простейшие элементы, показанные на рис, 8.55, б. Рассмотрим грамматику 6 =(У, Х, Р, 5) с У = =(А, В„5), ~,=(а, Ь, с) и ст производящими правилами —,( 1) 5-+.аА, 2) А-э. ЬА, З) Л ЬВ', 4)  — +с, где константы а, Ь и с приведе. ны на рис.

8.55,б. Как уже говорилось выше, 5 является на. чальпым символом, с которого д создаются все цепочки в языке Е(6). Если, например, после Рис. 8.86, Объект, иредставлеиимй своим скелетом (а), простейшие правила ! мы два раза при элементы (б) и структура, созданменим правило 2, то получим иья с иомошъкэ регулярной грвм- 5 =ь пА =ь- пЬА =ь. аЬЬА, где =.- матики (в), означает порядок вывода цепочки, начиная с 5 и применяя производящие правила из Р. Отметим, что производящие правила 5-ьаА и Л- ЬЛ трактуются как «из 5 может быть выведено аА» и «из А может быть выведено ЬА».

Поскольку в цепочке аЬЬА имеется переменная, то, применяя соответствующие правила, можно продолжить вывод. Например, если к ней два раза применить правило 2, а затем правила 3 и 4, то мы получим цепочку, которая соответствует структуре, приведенной на рис. 8,55,в.

Отметим, что после применения правила 4 цепочка не содержит переменных, и поэтому вывод прекращается. Нетрудно видеть, что приведенная выше грамматика имеет язык Е(6) = (аЬ"с(л '=в 1), где Ь" означает п повторений символа Ь. Другими словами, с помощью 6 можно 469 Производящие правила Семантическая яяформачн» Я-ьпА Связь с о можно осуществить только в месте, помеченном точкой. Направление и, которое обозначается 9, определяется направлением перпендикуляра, опущенного на линию, соединяющую концы двух отрезков, не помеченных точками )длина каждого огреака равна 3 см Связь с Ь осуществляется только в местах, помеченных точкачн.

Многократные связи недопустимы. Направление Ь совпадает с направлением о, и длина Ь равна 0,20 см. Это производящее правню можно применять не более !О раа ![вправления и и Ь должны совпадать Связи должны быть простылп1 и осунсествляться только в местах, помеченных точками Направления с и и должны совпалать. Связи должны быть простыми и осуществлячься в мес~ах, помеченных точкамн А-ьЬА А-ьЬВ В -и с Отметим, что, используя синтаксическую информацию, можно применить несколько синтаксических правил для описания относительно широкого класса моделей. Например, определив направление О, леы сможем не определять простейшие элементы для каждой возможной ориентации объекта.

Аналогично, требуя, чтобы все простейшие элементы имели одинаковое направление, мы исключаем из рассмотрения структуры гаечных ключей, лишенные физического смысла. Распознавание. До сих пор мы рассматривали грамматики как генераторы моделей образов. Ниже мы рассмотрим задачу распознавания, если дана цепочка, описывающая модель. При 470 создавать скелеты структур типа гаечных ключей произвольной длины в пределах разрешения, определяемого длиной простей. щего элемента Ь.

Лрииенеяиг сежантик, В рассмотренном выше примере леы неявно предполагали, что взаимосвязь между простейшими элементами устанавливается только в точках, показанных на рнс. 8.55,6, В более сложных ситуациях правила, устанавливаюгцие связи между элементами, а так!не другая информация относительно таких особенностей, как длина и направление простейших элементов, число применений правил, должна быть представлена в явном виде. Обычно это делается с помощью сел!антик. Как правило, синтаксис определяет структуру объекта или выражения, а семантика передает ее смысл. Например, предложение на Фортране А = В/С синтаксически правильно, но семантически корректно, только если СФ О. Для более ясного понимания этих понятий введем семантическую информацию для рассмотренной выше грамматики, предназначенной для описания формы гаечных ключей.

Эту информацию вместе с производящими правилами представим следующим образом: этом будем предполагать, что цепочка относится к языку ь(6), созданному грамматикой 6. Основные понятия, лежащие в основе синтаксического распознавания, можно проиллюстрировать математическими моделями вычислительных машин, называемых автожагахш.

Если на вход такого автомата подается цепочка, описывающая модель, то он способен распознать, относится ли эта модель к определенному языку или классу. Мы рассмотрим только конечнв!е автоматы, которые распознают языки, создаваемые регулярными грамматикамн. Конечный автомат определяется как пятерка А=(я, ~, Ь, е)а, Р), (8.5-11) где Π— конечное непустое множество состояний, Х вЂ” ко. нечный входная алфавит, ' функция перехода Ь устанавливает соответствие между множеством ьг Х Х (набором упорядоченных пар, образованных из элементов ьг и Х) и набором из всех подмножеств О, Рис, з.бб. Конечный антонах. с)о — начальное состояние и г" (подмножество из Я) — множество конечно!к или допустимых состояний. Эту терминологию и обозначения, связанные с выражением (8.5-! ! ), поясним на простом примере.

Пример. Рассмотрим автомат, заданный выражением (85-1!), где !г=(е)ю, д„!7а), Е =(а, Ь), Г=(с)о) и функция переходов состояния определяется выражением Ь= (с)о, а) = (с)а), Ь(фю Ь)=(ч!), Ь(йы а)=(с!а), Ь(фы Ь)=(с)а), Ь(ч„а)=.(ча), Ь(!7,, Ь)=(д!). Если, например, автомат находится в состоянии ао и на входе его символ а, то он пеРейдет в состоЯние с)а. Аналогично, если после символа а на входе появляется символ Ь, автомат перейдет в состояние д! и т.

д. Отметим, что в этом случае начальное и конечное состояния одно и то же. Диаграмма состояний для рассмотренного выше автомата приведена на рис, 8.56, На этой диаграмме каждое состояние обозначено вершиной, а направленные дуги указывают возможные переходы между состояниями, Конечное состояние обозначено двойной окружностью, и каждая дуга помечена символом, который вызывает этот переход. О цепочке в терминальных символов говорится, что она принилеиется или распознаегся автоматом, если, начиная нз состояния фм последовательность символов в ш переводит автомат в конечное состояние, посче того как на его входе был принят последний символ из ш.

На- 47! пример, автомат, приведенный на рис. 8.58, распознает цепочку и = аЬЬаЬЬ, но отбрасывает цвпочку св = ааЬаЬ. Между регулярными грамматиками и конечным автоматом имеется взаимно-однозначное соответствие, т, е. язык распознается конечным автоматом тогда и только тогда, когда он порождается регулярной грамматикой.

Процедура получения автомата, соответствующего данной регулярной грамматике, довольно ц оста. Пусть имеется грамматика 6 (У, ~„Р, Х,), где о — 5, и предположим, что в У входят Х, и и нетерминальных символов Хь Хз, ..., Х„. Множество состояний Я для автомата образуется в результате введения п+ 2 состояний (до, аь ...

..., дл, 2).„Д, таких, что су; соответствУет Х; длЯ О( с . =л и з7„, является конечным состоянием. Множество входных символов идентично множеству терминальных символов в 6. Функция перехода 6 определяется двумя правилами, основанными на правилах из 6. Для каждого с и 1, О ( г' я' и, О ~1=. и. 1. Если Хз — «аХ, находится в Р, то 6(ди а) содержит д« 2.

Если 5; — а находится в Р, то 6(д„а) содержит д„»~. Если же задан конечный автомат А = Я, Х, а, до, Р), то в соответствующей ему регулярной грамматике 6 =(А(, Х, Р, Хо) величина 72' является множеством состояний О с начальным символом Хо, соответствУющим с)о, а пРоизводЯщие пРавила 6 получаются следующим образом: 1. Если а~ находится в 6(д„а), то в Р имеется производящее правило Х~ — «аХ« 2. Если состояние нз Р находится в 6(Ф, а), то в Р имеется производящее правило Х; — а.

Пример. Конечный автомат, соответствующий приведенной выше грамматике, для описания моделей гаечных ключей можно построить, записав производящие правила следующим образом; Х, — аХь Х, — ЬХь Х, — ЬХ,, Хз- с. Тогда согласно изложенному выше, мы имеем А (С7, ~, 6, уо, Р), где О = = (чо Чю чз чз), д = (а, Ь, с), Р = (дз), и соответствие, устанавливаемое функцией переходов состояния Ь(до, а) = (д,), 6(271 Ь) = (Чп 472), (472, С) = (дз). ДЛя ПОЛНОТЫ МОЖНО ЗаПИСатЬ 6(уо, Ь)= 6(с)о, с)= 6(аь а) = 6(дь с)= 6(г(2, и)= 6(аз, Ь) =ф, где 7) — пустое множество, указывающее, что для данного автомата такие переходы не определены. Грамматики более высокой размерности, Рассмотренные выше грамматики пригодны для приложений, где связь между простейшими элементами удобно выражать цепочками. 11иже мы рассмотрим два прилзера грамматик, способных описывать более общие связи между простейшими элементами и частями моделей.

Характеристики

Список файлов книги