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


 

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

83536. Консульські імунітети та привілеї 34.97 KB
  В консульському праві як і в дипломатичному розрізняють дві категорії привілеїв та імунітетів: а привілеї та імунітети консульських установ; 6 привілеї та імунітети штатних консульських посадових осіб та інших працівників консульських установ. Найсуттєвішими в першій категорії є: недоторканність консульських приміщень; звільнення консульських приміщень від податків; недоторканність консульського архіву та документів; свобода зносин; безперешкодні зносини і контакти з громадянами держави що представляється. Другу категорію консульських...
83537. Право спеціальних місій 37.02 KB
  Функції спеціальної місії визначаються за взаємною згодою між державою що посилає і приймаючою державою. Для направлення або прийняття спеціальної місії не є необхідною наявність дипломатичних або консульських відносин між державами. За деякими виключеннями держава що посилає може на свій розсуд призначити членів спеціальної місії повідомивши попередньо приймаючій державі всю необхідну інформацію про чисельність і шал спеціальної місії і зокрема повідомивши про прізвища і посади осіб яких вона має намір призначити.
83538. Дипломатичне право міжнародних організацій 36.09 KB
  Як показує практика багатостороння дипломатія відбувається головним чином в рамках міжнародних організацій при яких держави засновують свої постійні представництва які користуються такими ж привілеями та імунітетами що і члени делегацій державчленів організації. Вона охоплює чотири сфери діяльності держав в їх відносинах з міжнародними організаціями і в рамках міжнародних конференцій а саме постійні представництва держав при міжнародних організаціях місії постійних спостерігачів при міжнародних організаціях делегації держав в органах і...
83539. Кодифікація міжнародного морського права. Види морських просторів 36.24 KB
  Міжнародне морське право являє собою систему міжнародноправових принципів і норм що визначають правовий режим морських просторів і регулюють відносини між державами та іншими суб\'єктами міжнародного права з приводу їх діяльності з дослідження та використання просторів Світового океану та його ресурсів. Міжнародне морське право відноситься до однієї з найбільш старих галузей міжнародного права і спочатку склалося у формі звичаєвих норм. Кодифікація морського права була проведена в XX ст.
83540. Внутрішні морські води та їх правовий режим 36.63 KB
  Внутрішні морські води це води розташовані в сторону берега від вихідної базисної лінії територіального моря. До складу внутрішніх морських вод входять: води заток бухт лиманів історичні затоки води морських портів а також води розташовані в сторону берега від вихідних ліній прийнятих для обчисленні ширини територіального моря. Води затоки відносяться до внутрішніх морських вод якщо її берега належать одній державі ширина природного входу до затоки не перевищує 24 морських миль Якщо відстань між пунктами природного входу до...
83541. Режим морських портів 36.21 KB
  Прибережна держава самостійно вирішує питання про характер порту зокрема його закритість або відкритість для міжнародного судноплавства. Прибережна держава не повинна проте відмовляти у дозволі на вхід до закритого порту судну яке знаходиться в небезпеці у випадку аварії або штормової погоди судну що зазнає лихо. З метою забезпечення власної безпеки прибережна держава може. Прибережна держава зазвичай не втручається у відносини між капітаном екіпажем та пасажирами.
83542. Правовий режим архіпелажних вод 38.18 KB
  Суверенна влада прибережної держави обмежена правом безперешкодного проходу та правом архіпелажного проходу морськими коридорами що надається іноземним морським та повітряним суднам в архіпелажних водах ст. Архіпелажний прохід морськими коридорами означає що усі судна і літальні апарати користуються правом архіпелажного проходу такими морськими коридорами і прольоту по таким повітряним коридорам з ціллю безперервного і швидкого транзиту через архіпелажні води з однієї частини відкритого моря або виключної економічної зони до іншої частини...
83543. Поняття і межі територіального моря. Право мирного проходу. Правовий режим територіальних вод 37.22 KB
  Правовий режим територіальних вод Територіальне море це пояс морських вод шириною до 12 морських миль що розташований між берегом чи безпосередньо за внутрішніми морськими водами або архіпелажними водами держави та відкритим морем або водами спеціальних зон. Територіальне море як й внутрішні морські води є частиною території прибережної держави. На підставі цього права торгівельні судна можуть проходити через територіальне море іноземної держави без спеціального дозволу лише за умови дотримання права прибережної держави. Прохід...
83544. Поняття та правовий режим прилеглої зони 36.05 KB
  Сстановлює що прилегла зона не може пролягати далі ніж на 12 морських миль від вихідної лінії від якої відміряється ширина територіального моря проте Конвенція з морського права 1982 р. містить положення що прилегла зона не може пролягати за межі 24 морських миль від цієї лінії Розвитком інституту прилеглої зони стала практика встановлення прибережними державами за межами свого територіального морязон виключного рибальства. Ширина морських зон виключного рибальства в практиці держав різниться.