22120

Система основных событий

Лекция

Коммуникация, связь, радиоэлектроника и цифровые приборы

Событие состоящее из всех слов входного алфавита всеобщее событие. F = {x1 v x2 v v xm} Событие содержащее все слова оканчивающиеся буквой xi. Событие содержащее все слова оканчивающиеся отрезком слова l1 S = F l1 Событие содержащее все слова начинающиеся с отрезка слова l1и оканчивающиеся на l2: S = l1 F l2 Событие содержащее только однобуквенные слова входного алфавита S = x1 v x2 v v xm Событие содержащее только двухбуквенные слова входного алфавита S = x1 v x2 v v xm x1 v x2 v v xm Событие содержащее все...

Русский

2013-08-04

28.5 KB

0 чел.

Лекция 6

Система основных событий.

В эти системы мы включим те из наиболее часто встречающихся событий, которые используются при записи регулярных выражений на практических занятиях и курсовой работе.

Пусть дан алфавит X{x1, x2, …, xm}.

  1.  Событие, состоящее из всех слов входного алфавита (всеобщее событие). F = {x1 v x2 v …v xm}
  2.  Событие, содержащее все слова, оканчивающиеся буквой xi.

     S = {x1 v x2 v …v xi v …v xm}xi = Fxi.

  1.  Событие, содержащее все слова, оканчивающиеся отрезком слова l1

     S = F l1

  1.  Событие, содержащее все слова, начинающиеся с отрезка слова l1и оканчивающиеся на l2: S = l1 F l2
  2.  Событие, содержащее только однобуквенные слова входного алфавита S = x1 v x2 v …v xm
  3.  Событие, содержащее только двухбуквенные слова входного алфавита S = (x1 v x2 v …v xm)( x1 v x2 v …v xm)
  4.  Событие, содержащее все слова длиной r

S = (x1 v x2 v …v xm)( x1 v x2 v …v xm)… (x1 v x2 v …v xm)

Всего r членов

  1.  Событие, содержащее все слова, длина которых кратна r

S = {(x1 v x2 v …v xm)( x1 v x2 v …v xm)… (x1 v x2 v …v xm)}

   r членов

  1.  Событие, состоящее из всех слов алфавита X{x1, x2}, не содержащих комбинации букв x1x1 и оканчивающихся буквой x2

S = {x2 v x1x2}

  1.   Событие, состоящее из всех слов алфавита X{x1, x2}, не содержащих серии из двух букв x1 и оканчивающихся буквой x2

S = {x2 v x1x2 v x1x1x2 v … v x1x1…x1x2}

            r-1 членов.

Рассмотрим пример составления регулярного выражения, определяющего закон функционирования конечного автомата.

 Пример. Записать в виде регулярного выражения алгоритм работы автомата, сравнивающего два двоичных числа, представленных в последовательном коде. Количество разрядов числа – произвольно.

x{x00, x01, x10, x11, xs}    y{y1, y2, y3}

Окончание чисел фиксируется подачей на вход автомата сигнала xs. Если число, поданное на первый вход автомата, меньше числа, поданного на второй вход, то КА выдает сигнал y1, если больше – то y2, если оба числа равны – то y3. Числа подаются на входы автомата младшими разрядами вперед. На входы автомата сравнения одновременно может поступить одна из четырех комбинаций сигналов 00, 01, 10, 11, которые закодируем следующим образом x00 =00, x01 = 01, x10 = 10, x11 = 11. При этом будем считать, что первая цифра каждой комбинации относится к первому входу, а вторая – ко второму входу. Таким образом, входной алфавит автомата включает пять букв X{x00, x01, x10, x11, xs},а выходной – три буквы Y{y1, y2, y3}.

Два двоичных числа равны, если равны цифры в любых одинаковых разрядах. Поэтому событие, заключающееся в поступлении на вход автомата равных чисел, состоит из всех возможных слов, содержащих буквы x00 и x11. Т. е. S3 = {x00 v x11}xs y3.

События, представленные в автомате сигналами y1 и y2 можно записать в виде:

S1 = {x00 v x01 v x10 v x11} x01 {x00 v x11} xs y1

S2 = {x00 v x01 v x10 v x11} x10 {x00 v x11} xs y2.

События S1, S2 и S3 не охватывают всего множества слов, которые могут быть записаны в алфавите X{x00, x01, x10, x11, xs}, т.к. в эти события входят только слова, оканчивающиеся буквой xs. Слова, не входящие в S1, S2 и S3, должны быть представлены в автомате пустой буквой e:

        

S4 = S1 v S2 v S3 e.

Очевидно, что записанные выражения можно упростить, если входные сигналы 00 и 11 закодировать одной буквой, например xr. Такое кодирование возможно, т.к. КА одинаково реагирует на эти комбинации.

S1 = {xr v x01 v x10} x01 {xr} xs y1

S2 = {xr v x01 v x10} x10 {xr} xs y2

S3 = {xr} xs y3

        

S4 = S1 v S2 v S3 e.

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

S1 v S2 = S2 v S1  - закон коммутативности

 (S1 v S2) v S3 = S1 v (S2 v S3) = S1 v S2 v S3

S1*(S2*S3) = (S1*S2)*S3 - законы ассоциативности

S1(S2 v S3) = S1S2 v S1S3 - закон дистрибутивности

{{S}} = {S}
       {S}*{S} = {S}

{{S1} v {S2} = {S1 v S2}

{e} = e

eS = Se = S


 

А также другие работы, которые могут Вас заинтересовать

28775. Специфика цивилизаций Древнего Востока и Античности 38.1 KB
  В восточной цивилизации не существует гарантий личных прав человека. Эссе Специфика цивилизации государства общества культуры Древнего востока и Античности Понятие цивилизации является очень широким. Специалисты выделяют три глобальных типа: традиционные цивилизации; индустриальная цивилизация; постиндустриальная информационная цивилизация. Цивилизации Востока развиваются циклически проходят фазы становления и упрочения единого государства его упадка а затем наступает катастрофа связанная с распадом государства.
28776. Место Средневековья во всемирно-историческом процессе 28.35 KB
  Место Средневековья во всемирноисторическом процессе. Как видно в оценке средневековья присутствуют крайности. Поразному определяются и временные рамки Средневековья. К тому же внутри тысячелетнего периода Средневековья принято выделять три этапа: Раннее Средневековье – Vв.
28777. Формирование древнерусской государственности. Принятие христианства и его влияние на дальнейшее развитие страны 111.82 KB
  Это тем более очевидно что классовые общества и государства в Скандинавии сложились позже чем на Руси и серьезно повлиять на формирование НовгородскоКиевской Руси варяги не могли.Роль варяжского элемента в ранних государственных структурах Древней Руси 4. И пошли за море к варягам к руси. Сказали Руси чудь славяне кривичи и весь: Земля велика и обильна а порядка в ней нет.
28778. Эволюция древнерусской государственности в XI-XII вв. Международные связи древнерусских земель 25.18 KB
  Международные связи древнерусских земель. Ее причинами были: раздел территории на уделы между наследниками различных ветвей Дома Рюриковичей происходил в результате действовавшего принципа по старшинству к старшему в роду; постоянные княжеские усобицы в основе которых часто лежали политические амбиции тех или иных конкретных лиц не согласных с лествичным правом; рост крупного землевладения укреплявший чувство уверенности в своих силах у крупных владетелей обладавших значительными материальными ресурсами; натуральный характер...
28779. Борьба народов Руси с иноземными захватчиками в XII в. 66.86 KB
  Борьба народов Руси с иноземными захватчиками в XII в. XIII век в истории Руси это время вооруженного противостояния натиску с востока монголотатары и северозапада немцы шведы датчане. Встают два важных вопроса: почему русские княжества проявив героизм и мужество не смогли дать отпор завоевателям Какие последствия имело для Руси иго Ответ на первый вопрос очевиден: конечно имело значение военное превосходство монголотатар жесткая дисциплина отличная конница прекрасно налаженная разведка и др. Другие подчеркивают...
28780. Держава Чингисхана и монгольские завоевания. Иго и дискуссия о его роли в становлении Русского государства 29.73 KB
  Влияние монголотатарского ига на развитие русских земель. Упомянув кратко о зависимости русских князей от ханских ярлыков и сбора налогов Соловьев отмечал что нет причины признавать значительное влияние монголов на русскую внутреннею администрацию поскольку мы не видим никаких его следов. произошло не благодаря а вопреки Орде с точки зрения на монгольское иго в современной исторической науке: Традиционная история рассматривает его как бедствие для русских земель. Нашествие кочевников сопровождались массовыми разрушениями русских городов...
28781. Начало самодержавия в России. Внутренняя и внешняя политика Ивана IV. Альтернативы развития страны: «Избранная Рада » и опричнина 17.93 KB
  Внутренняя и внешняя политика Ивана IV. Царствование Ивана Грозного принято условно делить на две части сильно отличающиеся друг от друга по внутренней политике. Это знаменовало формирование на Руси нового типа традиционного общества – сословнопредставительной монархии Постоянным же совещательным органом при царе служила еще со времен Ивана III Боярская дума состоявшая из бояр. Первый Земский собор орган сословного представительства обеспечивающий связь центра и мест речь Ивана IV с лобного места: осуждение неправильного боярского...
28782. Смута: социальная катастрофа или время альтернатив? Причины и последствия смутного времени. Начало династии Романовых 18.58 KB
  Смутное время началось после смерти Федора Ивановича последнего царя из рода Рюрика 6 января 1598 г. Русская армия в это время готовилась выйти на помощь Смоленску который с сентября 1609 года был осаждён войсками польского короля Сигизмунда III. Поляки и запорожцы овладели городами северской земли; население Стародуба и Почепа полностью погибло во время вражеского штурма; Чернигов и НовгородСеверский сдались.
28783. Понятие модернизации, ее виды и циклы. Особенности петровской модернизации 14.86 KB
  Первым этапом такой модернизации в России стали реформы Петра I Великого Основными предпосылками реформ были: 1 тупик развития 2 необходимость выхода к морям для развития экономики. Именно с этой даты ведется отсчет истории России как великой державы. Превращение России в великую и морскую державу символизировало принятие Петром Великим наследственного императорского титула.