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


 

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

18632. Схемы платежей в электронной коммерции 16.26 KB
  Схемы платежей в электронной коммерции Электронная коммерция от англ. ecommerce это сфера экономики которая включает в себя все финансовые и торговые транзакции осуществляемые при помощи компьютерных сетей и бизнеспроцессы связанные с проведением таких транзакций ...
18633. Классификация моделей. Основные виды моделей 16.36 KB
  Классификация моделей. Основные виды моделей. Классификация моделей По целям исследований В зависимости от целей исследования выделяют следующие модели: функциональные. Предназначены для изучения особенностей работы функционирования системы её назначения в
18634. Определение корпоративной информационной системы. Основ¬ные принципы комплексной автоматизации предприятия 14.45 KB
  Определение корпоративной информационной системы. Основные принципы комплексной автоматизации предприятия. КИС комплекс программ или программная система обеспечивающая основные бизнеспроцессы в компании. Корпоративной информационной системой КИС мы будем...
18635. Интерфейс: ввода/вывода, справочный 17.96 KB
  Интерфейс: ввода/вывода справочный. Связь пользователя с программами пакета можно представить как обмен сообщениями: либо пользователь передает в пакет некоторый запрос и получает на него ответ либо запрос формируется в пакете а от пользователя ожидается ответ. Для в
18636. Функции менеджмента 16.09 KB
  Функции менеджмента. Функции менеджмента являются составными частями любого процесса управления вне зависимости от особенностей размера назначения формы собственности и т.д. той или иной организации. Процесс управления менеджмента имеет пять взаимосвязанных функ
18637. Нейронные сети. Распознавание образов 542 KB
  Основные задачи, которые ставятся перед нейронными сетями, относятся к задачам распознавания образов. Они заключаются в том, чтобы классифицировать входной образ, то есть отнести его к какому-либо известному сети классу. Изначально сети даются эталонные образы – такие образы...
18638. Структурные единицы ЭВМ – элементы, узлы, блоки, устройства. Приведите примеры 13.85 KB
  Структурные единицы ЭВМ элементы узлы блоки устройства. Приведите примеры. Для составления полного представления о структуре ЭВМ необходимо рассмотреть ее элементную базу. Обычно при детализации структуры ЭВМ выделяют следующие структурные функциональные единицы...
18639. Анализ деловой активности предприятия 14.71 KB
  Анализ деловой активности предприятия Анализ деловой активности предприятия можно провести по следующим показателям: качественные показатели количественные показатели. 1.На качественном уровне предполагает анализ по так называемым неформализуемым критериям. Ре
18640. Организация связи предприятия с внешним миром 13.87 KB
  Организация связи предприятия с внешним миром. Виды связей организации с внешним окружением. Связи организации с внешней средой весьма трудно классифицировать вопервых ввиду их многофункциональности. Так властная регламентирующая связь может одновременно быть инф