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


 

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

76425. Запаздывающее звено и его свойства 45.78 KB
  Переходную функцию звена получим решив уравнение. Переходная характеристика звена приведена на рисунке. Переходная характеристика запаздывающего звена Импульсная переходная функция запаздывающего звена имеет вид: Импульсная переходная характеристика запаздывающего звена представлена...
76426. Виды соединений звеньев САУ 50.49 KB
  Соединение звеньев в САУ может выполняться в 3-х основных формах: последовательная, параллельная и соединение с обратной связью. Последовательное соединение звеньев (a)
76427. Правила преобразования структурных схем 90.16 KB
  Критерий правильности упрощения схемы заключается в равенстве входных и выходных сигналов упрощаемого участка до и после преобразования. Перенос сумматора через сумматор: а до преобразования; б после преобразования. Перенос узла через сумматор: а до преобразования; б после преобразования.
76428. Условия устойчивости линейных систем автоматического управления 93.58 KB
  Изменение регулируемой величины при произвольном внешнем воздействии представляет собой решение уравнения 3.22 первое слагаемое вынужденная составляющая имеющая тот же характер что и правая часть уравнения 3. Она определяется как частное решение неоднородного дифференциального уравнения 3.21 с правой частью: Второе слагаемое свободная переходная составляющая которая определяется общим решением однородного дифференциального уравнения 3.
76429. Критерий устойчивости Гурвица 61.79 KB
  Поэтому большее распространение получил алгебраический критерий устойчивости сформулированный в 1895 году математиком А. Критерий устойчивости сводится к тому что при должны быть больше нуля все определителей Гурвица получаемых из квадратной матрицы коэффициентов. Условия нахождения системы на границе устойчивости можно получить приравнивая нулю последний определитель: при положительности всех остальных определителей.
76430. Критерий устойчивости Михайлова 37.19 KB
  Критерий устойчивости Михайлова. 21: чтобы замкнутая система была устойчивой необходимо и достаточно чтобы годограф характеристического многочлена замкнутой системы годограф Михайлова начинался на положительной части действительной оси и проходил последовательно в положительном направлении исключая точку начала координат n квадрантов комплексной плоскости где n порядок характеристического уравнения. Графическое изображение годографов Михайлова для устойчивых и неустойчивых систем Практический пример Пусть характеристическое уравнение...
76431. КРИТЕРИЙ УСТОЙЧИВОСТИ НАЙКВИСТА 155.49 KB
  Предварительно должна быть определена устойчивость исследуемой системы в разомкнутом состоянии. Для неустойчивой разомкнутой системы нужно выяснить какое число корней ее характеристического полинома имеет положительные вещественные части. В одноконтурной системе составленной из последовательно соединенных звеньев корни характеристических полиномов этих звеньев являются одновременно корнями характеристического полинома разомкнутой системы. Если какоелибо звено в прямой цепи системы охвачено обратной связью то нужно определить корни...
76432. Структурные схемы систем автоматического управления 160.04 KB
  Структурная схема Структурная схема САУ схема САУ это изображение системы регулирования в виде совокупности динамических звеньев с указанием связей между ними. Структурная схема САУ может быть составлена на основе известных уравнений системы и наоборот уравнения системы могут быть получены из структурной схемы. Наименование Обозначение на структурной схеме Звено с одним входом Звено с двумя входами Узел разветвление Наименование Обозначение на структурной схеме Cумматор Элемент сравненияаналог сумматора Простейшие сочетания...
76433. Статические и астатические системы управления 21.21 KB
  В зависимости от принципа и закона функционирования ЗУ задающего программу изменения выходной величины различают основные виды САУ: системы стабилизации программные следящие и самонастраивающиеся системы среди которых можно выделить экстремальные оптимальные и адаптивные системы. обеспечивается неизменное значение управляемой величины при всех видах возмущений...