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


 

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

13320. ВИЗНАЧЕННЯ ПИТОМОЇ ТЕПЛОТИ ПАРОУТВОРЕННЯ РІДИНИ 236 KB
  Лабораторна робота № 5 ВИЗНАЧЕННЯ ПИТОМОЇ ТЕПЛОТИ ПАРОУТВОРЕННЯ РІДИНИ Мета роботи: а вивчення процесів пароутворення; б експериментальне визначення питомої теплоти пароутворення води при температурі кипіння. Прилади та матеріали: калориметр з мішалкою ки
13321. ВИЗНАЧЕННЯ КОЕФІЦІЄНТА ПОВЕРХНЕВОГО НАТЯГУ РІДИНИ МЕТОДОМ ВІДРИВУ КІЛЬЦЯ 168.5 KB
  Лабораторна робота № 6 ВИЗНАЧЕННЯ КОЕФІЦІЄНТА ПОВЕРХНЕВОГО НАТЯГУ РІДИНИ МЕТОДОМ ВІДРИВУ КІЛЬЦЯ. Мета роботи: а вивчення властивостей рідкого стану речовини; б визначення коефіцієнта поверхневого натягу рідини від типу речовини; в визначення залежності коефі
13322. Визначення коефіцієнта Пуасона методом Клемана і Дезорма 473 KB
  Лабораторна робота №8 Визначення коефіцієнта Пуасона методом Клемана і Дезорма. Мста роботи: аВивчення законів ідеального газу. бЕкспериментальне визначення показника адіабати. Прилади і матеріали: балон з двома кранами рідинний манометр ручний насос. Кор...
13323. Визначення теплоти розчинення солі 460 KB
  Лабораторна робота № 9. Визначення теплоти розчинення солі. Мета роботи: адослідним шляхом визначити теплоту розчинення солі; бустановити залежність теплоти розчинення солі від концентрації розчину. Прилади та матеріали: посудина Дюара термометр мензурка сі...
13324. ВИЗНАЧЕННЯ КОЕФІЦІЄНТА ВНУТРІШНЬОГО ТЕРТЯ ТА СЕРЕДНЬОЇ ДОВЖИНИ ВІЛЬНОГО ПРОБІГУ МОЛЕКУЛ ПОВІТРЯ 400 KB
  Лабораторна робота № 10 ВИЗНАЧЕННЯ КОЕФІЦІЄНТА ВНУТРІШНЬОГО ТЕРТЯ ТА СЕРЕДНЬОЇ ДОВЖИНИ ВІЛЬНОГО ПРОБІГУ МОЛЕКУЛ ПОВІТРЯ Мета роботи: а вивчення основних законів молекулярнокінетичної теорії газів; б експериментальне визначення основних параметрів молекулярн...
13325. ВИЗНАЧЕННЯ КОЕФІЦІЄНТА ЛІНІЙНОГО РОЗШИРЕННЯ ТВЕРДИХ ТІЛ 696 KB
  Лабораторна робота №11 ВИЗНАЧЕННЯ КОЕФІЦІЄНТА ЛІНІЙНОГО РОЗШИРЕННЯ ТВЕРДИХ ТІЛ Мета роботи: авивчення термічного розширення твердих тіл; бекспериментальне визначення коефіцієнта лінійного розширення різних матеріалів. Прилади та матеріали: прилад для в...
13326. Визначення вязкості рідини капілярним віскозиметром 365 KB
  Лабораторна робота № 12 Визначення вязкості рідини капілярним віскозиметром. Мета роботи: авивчення властивостей рідини; бекспериментальне визначення коефіцієнта вязкості рідини. Прилади та матеріали: віскозиметр секундомір спирт дистильована вод
13327. Визначення коефіцієнта поверхневого натягу методом Ребіндера 223 KB
  Лабораторна робота №7 Визначення коефіцієнта поверхневого натягу методом Ребіндера. Мета роботи: аВизначення властивостей рідини: бВивчення методів та експериментальне визначення коефіцієнта поверхневого натягу. Прилади та матеріали: аспіратор установка
13328. Комп’ютерний вибір оптимальних однорідних термоелектричних матеріалів для термоелектрики 29.5 KB
  Звіт до лабораторної роботи № 1 Компютерний вибір оптимальних однорідних термоелектричних матеріалів для термоелектрики Мета роботи Використовуючи експериментальні дані кінетичних коефіцієнтів навчитись проводити раціональний вибір термоелектричного мат