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


 

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

15814. ИССЛЕДОВАНИЕ ОПТИЧЕСКИХ ПЛЕНОК ФТОРИДОВ И БИФТОРИДОВ 655.5 KB
  ИССЛЕДОВАНИЕ ОПТИЧЕСКИХ ПЛЕНОК ФТОРИДОВ И БИФТОРИДОВ Со времен своего возникновения технология изготовления многослойных интерференционных покрытий ИП занимающая целую отрасль в оптическом приборостроении претерпела значительные изменения. Современные средства...
15815. МЕТОДЫ АНАЛИЗА УСТОЙЧИВОСТИ ОПТИЧЕСКИХ ИНТЕРФЕРЕНЦИОННЫХ ПОКРЫТИЙ 3.56 MB
  МЕТОДЫ АНАЛИЗА УСТОЙЧИВОСТИ ОПТИЧЕСКИХ ИНТЕРФЕРЕНЦИОННЫХ ПОКРЫТИЙ При решении задач проектирования и изготовления тонкопленочных оптических интерференционных покрытий особое внимание уделяется исследованию воспроизводимости их спектральных характеристик [17]. ...
15816. Microsoft Sql Server 2005. Представления 117 KB
  Microsoft Sql Server 2005. Представления Представления Представления – это именованные запросы на выборку данных инструкции SELECT на языке TSQL хранящиеся в базе данных. В запросах представления можно использовать так же как и таблицы независимо от сложности их инструкций SELECT.
15817. Microsoft SQL Server 2005. Хранимые процедуры 87 KB
  Microsoft SQL Server 2005. Хранимые процедуры Хранимые процедуры Хранимая процедура это наиболее часто используемая в базах данных программная структура представляющая собой оформленный особым образом сценарий вернее пакет который хранится в базе данных а не в отдельном ...
15818. SQL Server 2005. Программирование на T-SQL 78.5 KB
  SQL Server 2005. Программирование на TSQL Программирование на TSQL Синтаксис и соглашения TSQL. Правила формирования идентификаторов Все объекты в SQL Server имеют имена идентификаторы. Примерами объектов являются таблицы представления хранимые процедуры и т.д. Идентификато
15819. Начало работы с Microsoft SQL Server 2005 187 KB
  Начало работы с Microsoft SQL Server 2005 Утилита SQL Server Management Studio Подавляющую массу задач администрирования SQL Server можно выполнить в графической утилите SQL Server Management Studio. В ней можно создавать базы данных и все ассоциированные с ними объекты таблицы представления ...
15820. Основы Transact SQL: Добавление, изменение и удаление данных 63 KB
  Основы Transact SQL: Добавление изменение и удаление данных. Основы Transact SQL: Добавление изменение и удаление данных в таблицах Запросы рассмотренные ранее были направлены на то чтобы получить данные содержащиеся в существующих таблицах базы данных. Главным ключевым сло...
15821. Основы Transact SQL: Простые выборки данных 241.5 KB
  Основы Transact SQL: Простые выборки данных SQL это аббревиатура выражения Structured Query Language язык структурированных запросов. SQL основывается на реляционной алгебре и специально разработан для взаимодействия с реляционными базами данных. SQL является прежде всего инфор...
15822. Основы Transact SQL: Простые выборки данных 199.5 KB
  Основы Transact SQL: Простые выборки данных Создание вычисляемых полей Конструкция SELECT кроме имен столбцов таблиц может также включать так называемые вычисляемые поля. В отличие от всех выбранных нами ранее столбцов вычисляемых полей на самом деле в таблицах базы дан...