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


 

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

45491. Моделирование случайных чисел с заданным 34.5 KB
  Для этого непрерывный закон распределения вероятности события дискретизируем. hi высота iого столбца fx распределение вероятности показывает насколько вероятно некоторое событие. Если точка в пересечении этих двух координат лежит ниже кривой плотности вероятности то событие X произошло иначе нет. Метод взятия обратной функции Допустим задан интегральный закон распределения вероятности где fx функция плотности вероятности.
45492. Оценка точности модели 76 KB
  Преобразование Фурье Преобразование Фурье Модель сигнала Способ основывается на том что в любом сигнале присутствуют гармонические составляющие. Сумма гармоник с соответствующими весами составляет модель сигнала. Пусть задан сигнал: Определяем время рассмотрения сигнала: если сигнал периодический то время рассмотрения равно периоду p сигнала; b если сигнал непериодический то периодом сигнала считается все время его рассмотрения. Отметим важную особенность данного способа представления вместо всего сигнала во всех его подробностях...
45493. Регрессионные модели 85.5 KB
  Линейная одномерная модель: y =0 1 x Ei = Yi 0 1 Xi i = 1n где n число снятых экспериментально точек. Ошибки всех точек i от 1 до n следует сложить. Найдем значение sigm по формуле: Если в интервал Yэ Yт Yэ попадает 67 точек и более то выдвинутая нами гипотеза принимается. Если требуется большая уверенность в результате то используют дополнительное условие: в интервал Yэ 2 Yт Yэ 2 должны попасть 95 экспериментальных точек.
45494. Методы построения датчиков случайных чисел 75.5 KB
  Генератор случайных чисел ГСЧ Основа метода МонтеКарло ГСЧ равномерно распределенных в интервале 01. Такая последовательность чисел должна обладать математическим ожиданием и дисперсией Если окажется что случайные числа должны быть распределены в другом интервале то преобразование имеет вид: ГСЧ ррb x:= b r Пример: x:= 313r r:=0 x:=3r:=1 x:=10r:=0. ГСЧ порождает случайный поток событий с равномерным законом распределения. ГСЧ делятся на: физические; табличные; алгоритмические.
45495. Общие принципы построения моделирующих алгоритмов 47.5 KB
  Общие принципы построения моделирующих алгоритмов Проблема при составлении алгоритмов на последовательной машине состоит в том что при моделировании необходимо отслеживать множество параллельных процессов во времени. Основные методы Принцип Принцип особых состояний Принцип последовательной проводки заявок Принцип параллельной работы объектов Принцип Определение состояния системы в фиксированные моменты времени: t t t2 Особенности: самый универсальный и простой метод описывает широкий класс объектов Недостатки: самый...
45496. Иерархия протоколов 304 KB
  Информационная совместимость – это правила передачи информации от одного узла к другому. Для того чтобы передать информацию от одного узла другому используют как минимум три уровня: физический; канальный; сетевой; На физическом уровне описаны характеристики передающей среды Основной задачей канального уровня является преобразование физической среды в канал передачи данных а так же выявление ошибок и деление информации на кадры. Кадр – единица измерения для передачи информации для сетей. Первые четыре уровня обеспечивают...
45497. Теоретические основы передачи данных 378.5 KB
  Ограничения на пропускную способность передачи данных.5c ∑ n sin2pnft∑ bncos2pnft f – частота nbn – амплитуды nой гармоники t – время передачи сигнала gt – определенное ограничение на пропускную способность. При этом скорость передачи информации зависит от способа кодирования и скорости изменения кодирования.
45498. Магистрали 261 KB
  Основное достижение – это применение одного канала для передачи сигналов между различными источниками и приемниками. Основано на разделении передачи сигналов от разных источников по различным несущим частотам. Это связано с тем что пропускная способность составляет 25000 Гц и за счет этого в оптических каналах скорость передачи на порядок выше. Это связано с тем что после получения канала с аналоговой петли скорость передачи данных может быть увеличена в несколько раз поэтому для цифровых каналов связи применяется метод мультиплексирования...
45499. Коммутация 466 KB
  Для систем передачи используются три способа коммутации: коммутация сообщений; коммутация каналов; коммутация пакетов. При использовании коммутации каналов снижаются накладные расходы на передачу информации. При коммутации пакетов все сообщения разделяются на определенные пакеты. В отличие от коммутации каналов абонент не может монополизировать линию.