лекции, страница 22

PDF-файл лекции, страница 22 Тестирование на основе моделей (63507): Лекции - 9 семестр (1 семестр магистратуры)лекции: Тестирование на основе моделей - PDF, страница 22 (63507) - СтудИзба2020-08-21СтудИзба

Описание файла

PDF-файл из архива "лекции", который расположен в категории "". Всё это находится в предмете "тестирование на основе моделей" из 9 семестр (1 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр PDF-файла онлайн

Текст 22 страницы из PDF

В наблюдаемодетерминированном новое состояние можно однозначно определить, зная предыдущее,принятый стимул и выданную реакцию.Для детерминированного автомата (S, s0, I, O, T) пусть δ и λ обозначают функциипереходов и вывода, т.е. (s1, i, o, s2) ∈ T тогда и только тогда, когда δ(s1, i) = s2, и λ(s1, i) = o.Оба этих отображения можно расширить до отображений состояния и принятойпоследовательности стимулов в последовательность реакций и итоговое состояние. Именно,для состояния автомата s ∈ S и последовательности входных символов α ∈ Ι* определим δ(s,α) ∈ S и λ(s, α) ∈ O* рекурсивно следующим образом.Если α — пустая последовательность ε, то δ(s, α) = s и λ(s, α) = ε.Если α — непустая и α = α’a, где α’ ∈ Ι* и a ∈ Ι, то δ(s, α) = δ(δ(s, α’), a) и λ(s, α) = λ(s,α’)λ(δ(s, α’), a).Конечный автомат реализует некоторое соответствие последовательностей символов из Iи последовательностей символов из O, φ ⊆ I*×O*.

Это соответствие называется егоповедением. Для детерминированных автоматов φ = λ(s0, ⋅), то есть поведение являетсяотображением входных последовательностей в выходные для начального состояния.С точки зрения внешнего наблюдателя, не имеющего возможности «увидеть» текущеесостояние автомата, два автомата с одинаковым поведением неотличимы. Точно также длянего неотличимы состояния, в которых на одну и те же последовательности входныхсимволов всегда может быть выдана одна и та же последовательность реакций.

Такиесостояния (даже в разных автоматах) называются эквивалентными или неотличимыми.Автоматы называются эквивалентными, если эквивалентны их начальные состояния.Для любого автомата можно построить эквивалентный ему наблюдаемодетерминированный автомат. Этот факт доказывается примерно так же, как возможностьиспользовать детерминированный автомат в качестве распознавателя регулярного языка.Понятно, что внешнему наблюдателю отличить друг от друга эквивалентные автоматыневозможно.

Чаще всего, это и не нужно, поскольку автомат обычно предназначен как раздля того, чтобы реализовывать некоторое соответствие между входными и выходнымипоследовательностями, и любой автомат, делающий это правильно, считается подходящим.Поэтому с точки зрения тестирования автоматов важен только их класс эквивалентности.В каждом классе эквивалентности автоматов есть единственный (с точностью доизоморфизма, т.е. взаимно-однозначного отображения состояний, сохраняющего начальноесостояние и сопоставляющего эквивалентные) автомат с минимальным числом состояний.Такой автомат называют минимальным или приведенным. При тестировании обычнопытаются проверить соответствие как раз минимальному автомату, описывающемутребуемое поведение тестируемой системы.Специальные типы входных последовательностей автоматовЧтобы уметь проверять соответствие поведение неизвестного автомата заданному, нужноуметь различать автоматы, у которых различия в поведении есть.

Для этого используетсянесколько техник, основанных на специфических входных последовательностях.Далее все определения даются для детерминированных автоматов. Для некоторых из этихпонятий есть аналоги для автоматов общего вида, но их определения более сложны.Идентификация состоянийРазличающая последовательность (distinguishing sequence) конечного автомата — этотакая конечная последовательность стимулов d ∈ Ι*, что соответствующие ейпоследовательности реакций в разных состояниях автомата разные.

То есть, ∀s1, s2 ∈ S s1 ≠ s2⇒ λ(s1, d) ≠ λ(s2, d).a/xa/xb/x01b/yb/ya/y2Рисунок 1. Пример конечного автомата, имеющего различающую последовательность.Например,вавтомате,изображенномнарисункевышеразличающейпоследовательностью является последовательность ab, поскольку выполнено λ(0, ab) = xy,λ(1, ab) = xx, λ(2, ab) = yy.Адаптивной последовательностью в алфавитах I и O называется дерево с корнем, чьивершины помечены элементами I, а ребра помечены элементами O. Длиной адаптивнойпоследовательности называется максимальное число вершин в цепочках ее вершин от корнядо листовой.К конечному автомату в определенном состоянии можно применять не только обычныепоследовательности, но и адаптивные.

Результатом такого применения можно считатьотображение цепочки вершин адаптивной последовательности, начинающейся от корня ипродолжающейся вдоль его ребер, в выходной алфавит автомата. На это отображениенакладывается следующие два ограничения.•Если оно определено для некоторой вершины и его значение совпадает с меткойодного из ведущих из нее ребер, оно должно быть определено и для конца этогоребра.•Если оно определено для одного из потомков некоторой вершины, оно должны бытьопределено и для самой вершины и значение его на этой вершине должно совпадатьс пометкой ребра, ведущего к указанному потомку.Интуитивно применение адаптивной последовательности можно описать так: мыприменяем к автомату последовательно, начиная от корня, стимул, стоящий в очереднойвершине, смотрим на полученную реакцию, и если она совпадает с пометкой одного изребер, ведущих из текущей вершины, идем по нему и применяем стимул, стоящий в егоконце, и т.д.Обычная различающая последовательность называется также статической различающейпоследовательностью.

Адаптивной различающей последовательностью автомата называетсятакая адаптивная последовательность в его алфавитах стимулов и реакций, что результаты ееприменения во всех состояниях различны.Например, для представленного выше автомата в качестве адаптивной различающейпоследовательности можно взятьxa⎯⎯→bДлина этой адаптивной последовательности такая же, как у статической, но она позволяетбыстрее определить состояние 2 — для этого достаточно получить y в ответ на a.Различающие последовательности, как статические, так и адаптивные, позволяютоднозначно определять состояние автомата, в котором они были применены.

Однако не увсякого автомата они есть. Ясно, что из существования статической различающейпоследовательности следует существование адаптивной. Более того, есть примерыавтоматов, у которых нет статической различающей последовательности, но есть адаптивная.Ниже показан пример автомата, у которого нет даже адаптивной различающейпоследовательности.a/xb/ya/x01b/xb/xb/y3a/y2a/yРисунок 2. Пример автомата без различающей последовательности.Чтобы убедиться в этом, достаточно проанализировать результаты применения a и b (поотдельности) к этому автомату.

Различающая последовательность не может начинаться с a,поскольку после этого стимула перестают быть различимы пары состояний 0 и 1, 2 и 3 —после принятия a в любом из состояний пары автомат оказывается в одном и том жесостоянии, выдав при этом одну и ту же реакцию. Точно так же b «слепляет» пары состояний0 и 3, 1 и 2, поэтому различающая последовательность не может начинаться с b.Чтобы различать состояния при отсутствии различающей последовательности,необходимы другие техники.Последовательностью однозначных входов/выходов или UIO-последовательностью(unique input-output sequence) для данного состояния s называется такая последовательностьстимулов u, что результат ее применения в состоянии s отличается от результатов ееприменения во всех других состояниях.

То есть, ∀s1 ∈ S s1 ≠ s ⇒ λ(s, u) ≠ λ(s1, u).Различающая последовательность является UIO-последовательностью сразу для всехсостояний автомата. В автомате, изображенном на Рис. 1, UIO-последовательностью длясостояния 1 является также b, а для состояния 2 — a.Есть автоматы, в которых нет различающих последовательностей, ни статической, ниадаптивной, но для каждого состояния есть UIO-последовательность. К сожалению, бываюти автоматы, ни одно состояние которых не имеет UIO-последовательности. Примеризображен на Рис.

2.В таких случаях можно использовать характеризующее или диагностическое множествопоследовательностей (characterizing set) W автомата. Это такое множество входныхпоследовательностей, что для каждых двух разных состояний автомата в нем найдетсяпоследовательность, результаты применения которой в этих состояниях различны. То есть,∀s1, s2 ∈ S s1 ≠ s2 ⇒ ∃α ∈ W λ(s1, α) ≠ λ(s2, α).Диагностическое множество всегда существует для минимального автомата, поскольку внем поведение в разных состояниях отличается. Для автомата, имеющего различающуюпоследовательность d, можно в качестве W взять {d}.

Для автомата, в котором все состоянияимеют UIO-последовательности любое множество, содержащее по UIO-последовательностидля каждого состояния, является диагностическим. Для автомата, изображенного на Рис. 2,диагностическим является множество {a, b} — легко проверяется, что возможные реакции наэто множество во всех его состояниях различны.Для вычисления статической и адаптивной различающих последовательностей, UIOпоследовательностей и диагностического множества можно использовать следующийалгоритм.Упорядочим каким-либо образом множество I.

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

Делать это можноитеративно, основываясь на результатах таких же вычислений для префиксов даннойпоследовательности.b/xb/x0a/x1a/y2a/x, b/xa/y, b/x5a/x, b/x4a/y, b/x3Рассмотрим автомат, изображенный на рисунке выше. Попробуем применить к нему этоталгоритм.abaaabbabb0 x/1x/0xy/2xx/0xx/1xx/01 y/2x/0yx/3yx/3xx/1xx/02 x/3x/3xy/4xx/4xy/4xx/43 y/4x/4yx/5yx/5xx/5xx/54 x/5x/5xy/0xx/0xy/0xx/05 y/0x/0yx/1yx/0xx/1xx/0{0,2,4}x{0,2,4}xy {0,2,4}xx {0,1,3,5}xx{1,3,5}y{1,3,5}yx {1,3,5}yx {2,4}xyx{1,3,5}yx{1,3,5} xx{0,4}xx{1,5}y{0,2,4}xy{0,2,4} yx{0,3,5} xy{0,4}После построения разбиений для всех последовательностей длины 2 видно, чтомногократное применение a не будет давать новой информации, просто сдвигая текущеесостояние по циклу.

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