Главная » Просмотр файлов » Робототехника.Фу, Ли, Гонсалес

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

Файл №962794 Робототехника.Фу, Ли, Гонсалес (Робототехника.Фу, Ли, Гонсалес) 80 страницаРобототехника.Фу, Ли, Гонсалес (962794) страница 802013-09-29СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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иже мы рассмотрим два прилзера грамматик, способных описывать более общие связи между простейшими элементами и частями моделей.

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

Тип файла
DJVU-файл
Размер
6,01 Mb
Тип материала
Высшее учебное заведение

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

Свежие статьи
Популярно сейчас
А знаете ли Вы, что из года в год задания практически не меняются? Математика, преподаваемая в учебных заведениях, никак не менялась минимум 30 лет. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6439
Авторов
на СтудИзбе
306
Средний доход
с одного платного файла
Обучение Подробнее