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


 

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

13034. Транзисторный стабилизатор напряжения 711 KB
  Лабораторная работа №7. Транзисторный стабилизатор напряжения. Цель работы: Знакомство и исследование одной из схем стабилизатора напряжения снятие его характеристик. Приборы: Измерительная панель лабораторного стенда. Электронный вольтметр. Авомет
13035. Операционные усилители. Обратная связь, ее влияние на характеристики радиоэлектронных схем (на примере операционных усилителей) 295.5 KB
  Лабораторная работа №9 Операционные усилители. Обратная связь ее влияние на характеристики радиоэлектронных схем на примере операционных усилителей. Цель работы: изучение операционных усилителей и схем выполненных на их основе; исследование влияния обратной с...
13036. Исследование процессов амплитудной модуляции и детектирования амплитудно-модулированных колебаний 208 KB
  Лабораторная работа № 11. Цель работы: исследование процессов амплитудной модуляции и детектирования амплитудно-модулированных колебаний; знакомство со схемами простого радио-передающего и радиоприемного устройств. Приборы: 1. Испытательная панель лаб...
13037. Теплотехника. Методические указания к выполнению лабораторных работ 639.5 KB
  Методические указания к выполнению лабораторных работ по дисциплине Теплотехника для студентов специальностей Методические указания к выполнению лабораторных работ составлены в соответствии с программой по дисциплине Теплотехника для студентов специальнос
13038. ЖКХ. Бухгалтерский учет 1.6 MB
  ЖКХ. Бухгалтерский учет. Согласно общемировой тенденции перехода к смешанной экономике сочетающей различные формы собственности на средства производства в России взят курс на формирование эффективной социально ориентированной рыночной системы. Представление о неэффективност
13039. Расчет котельной установки 7.02 MB
  Курсовой проект Расчет котельной установки Введение Котлы типа ДКВР используются в различных отраслях промышленности сельском и коммунальном хозяйстве. Котлы ДКВР отличаются достаточно высокой экономичностью небольшой массой простотой конструкции малыми
13040. Разработка информационной системы оплата услуг ЖКХ 707.5 KB
  КУРСОВАЯ РАБОТА ПО ДИСЦИПЛИНЕ РАЗРАБОТКА И ЭКСПЛУАТАЦИЯ ИНФОРМАЦИОННОЙ СИСТЕМЫ НА ТЕМУ: Разработка информационной системы оплата услуг ЖКХ СОДЕРЖАНИЕ Введение Глава 1. Теоретическая часть. Описание предметной области 1.2. Описание первичных ...
13041. Управление финансами предприятия в сфере ЖКХ 319.5 KB
  Курсовая работа По дисциплине: Финансы организаций На тему: Управление финансами предприятия в сфере ЖКХ Содержание: Введение Глава 1. Теоретические основы понятие жилищнокоммунального хозяйства и его финансов Состояние ЖКХ в России О жилищноко...
13042. Жилищно-коммунальное хозяйство (ЖКХ) 277.12 KB
  Содержание Введение Структура и экономическое состояние отрасли Региональные особенности жилищнокоммунального хозяйства Стимулирование создания товариществ собственников жилья Антимонопольное регулирование и создание конкурентной среды в те