22105

Общие правила подчинения мест регулярного выражения

Лекция

Коммуникация, связь, радиоэлектроника и цифровые приборы

Определим вначале внутренние состояния в которые переходит автомат из состояния 0 при подаче на его вход сигнала x1. Следовательно автомат из состояния 0 под действием сигнала x1 переходит в состояние 2. Аналогично сигнал x2 переводит автомат из состояния 0 в состояние 1 т. Отсюда получаем следующую отмеченную таблицу переходов: yg e e e e e e y1 e y2 xj ai 0 1 2 3 4 5 6 7 8 x1 2 2 4 2 6 2 7 7 2 x2 1 1 3 1 5 1 8 8 1 yg E e e y1 e y2 xj ai A0 a1 a2 a3 a4 a5 x1 A1 a2 a3 a4 a4 a1 x2 A0 a0 a0 a5 a5 a0 Из построенной таблицы видно что из...

Русский

2013-08-04

54.5 KB

0 чел.

Лекция 8

Сформулируем теперь общие правила подчинения мест регулярного выражения.

  1.  Индекс места перед любыми скобками распространяется на начальные места всех дизъюнктивных членов, записанных в этих скобках.
  2.  Индекс конечного места, любого дизъюнктивного члена, заключенного в любые скобки, распространяется на место, непосредственно следующее за этими скобками.
  3.  Индекс места перед итерационными скобками распространяется на место, непосредственно следующее за этими скобками.
  4.  Индекс конечного места любого дизъюнктивного члена, заключенного в итерационные скобки, распространяется на начальные места всех дизъюнктивных членов, заключенных в эти итерационные скобки.
  5.  Индексы мест, слева и справа от которых стоят буквы, никуда не распространяются.
  6.  В автоматах многократного действия индекс конечного места всего выражения распространяется на те же места, на которые распространяется индекс начального места. Это правило справедливо только в тех случаях, когда событие представлено регулярным выражением так, что оно не содержит многократно повторяющихся слов, входящих в заданное событие. И тогда организация автомата многократного действия осуществляется путем разметки.

Смысл приведенных правил подчинения мест сводится к следующему: основному месту с индексом i подчиняется место j, если автомат, находящийся в состоянии i, может принять букву входного алфавита, записанную непосредственно справа от места j.

По размеченному регулярному выражению теперь можно составить таблицу переходов автомата. Однако перед построением таблицы целесообразно уменьшить число индексов основных мест, а следовательно и число внутренних состояний автомата.

На этом первом этапе минимизации внутренних состояний можно пользоваться следующим правилом:

Если несколько предосновных мест отмечено одинаковой совокупностью индексов и справа от этих мест записаны одинаковые буквы, можно отметить одинаковыми индексами.

В полученном нами выражении основные места 2, 4 и 7 можно отметить общим индексом, т.к. слева от каждого из этих мест записана буква x1, а предосновные места, предшествующие этой букве, имеют одинаковую совокупность индексов (0, 1, 3, 6, 11). Теперь с учетом этого проведем новую разметку.

S = { x2 v x1 x2 v x1 x1 x2} x1 x1 x1 { x1 } x2  

     0       1         2    3        2    4    5        2   6    7       8        9

          0 0    2        0    2    4        0     2   6       7        7

 1 1       1                    1                  8        8

 3 3       3                    3

 5 5       5                    5

 9 9              9                    9

На этом первый этап минимизации (минимизации по регулярному выражению) закончен.

Составим теперь отмеченную таблицу переходов автомата. Определим вначале внутренние состояния, в которые переходит автомат из состояния 0 при подаче на его вход сигнала x1. Для этого найдем все предосновные места, содержащие индекс 0, справа от которых записана буква x1. Таких мест в выражении три. Все основные места, расположенные за этой буквой x1, отмечены индексом 2. Следовательно, автомат из состояния 0 под действием сигнала x1 переходит в состояние 2. Аналогично, сигнал x2 переводит автомат из состояния 0 в состояние 1, т.к. за предосновным, содержащим индекс 0, после буквы x2 расположено основное место с индексом 1. Таким же образом  определяются переходы автомата их других внутренних состояний. Сигнал y1 выдается после поступления подряд трех букв x1, т.е. в состоянии 6, а сигнал y2 – после x2, следующей за серией из трех и более букв, т.е. в состоянии 8. В остальных случаях выдается пустая буква е. Отсюда получаем следующую отмеченную таблицу переходов:

yg

e

e

e

e

e

e

y1

e

y2

xj\ai

0

1

2

3

4

5

6

7

8

x1

2

2

4

2

6

2

7

7

2

x2

1

1

3

1

5

1

8

8

1

yg

E

e

e

y1

e

y2

xj\ai

A0

a1

a2

a3

a4

a5

x1

A1

a2

a3

a4

a4

a1

x2

A0

a0

a0

a5

a5

a0

Из построенной таблицы видно, что из состояний 0, 1,3 и 5 автомат сигналами x1 и x2 переводится в одинаковые состояния (2 и 1). Кроме того, все перечисленные состояния отмечены одинаковыми выходными сигналами. Поэтому состояния 0, 1, 3 и 5 можно объединить в одно состояние, обозначив его как а0. Введем также обозначения: 2 – а1; 4 – а2; 6 – а3; 7 – а4; 8 – а5. Тогда получим упрощенную таблицу переходов автомата. В этой таблице из состояний а3 и а4 под действием входных сигналов х1 и х2 автомат переходит в одинаковые состояния а4 и а5. Но объединять эти состояния нельзя, т.к. отмечены разными выходными сигналами. По этой же причине нельзя объединять состояния а0 и а5. Объединение состояний и составляет второй этап минимизации, причем объединяются только такие состояния, которые отмечены одинаковыми выходными сигналами, и из которых под действием одинаковых входных сигналов происходит переход в одинаковые состояния. Очевидно, у таких состояний должны совпадать столбцы таблицы переходов.

Рассмотрим еще один пример абстрактного синтеза автомата. Найдем таблицу переходов автомата сравнения чисел, условия работы которого заданны регулярными выражениями

S3 = |{|x2|}|xs|; S1 = |[|x2|v|x01|v|x10|}|x01|{|x2|}|xs|;

S2 = |{|x2|v|x01|v|x10|}|x10|{|xr|}xs

Регулярные выражения событий S1 и S2 содержат одинаковые сомножители в итерационных скобках, перед которыми расположено место с индексом 0. Поэтому в обоих выражениях основные места внутри итерационных скобок отмечены одинаковыми индексами (3, 4 и 5). Индекс конечного места каждого выражения распространяется на начальные места всех регулярных выражений, т.к. в автоматах многократного действия за словом любого события, например S1, может быть подано слово любого другого события, т.е. S2 v S2 v S3. В размеченных выражениях можно объединить места с индексами 4, 6 и 5,9:

S3 = |{|x2|}|xs|; S1 = |[|x2|v|x01|v|x10|}|x01|{|x2|}|xs|;

S2 = |{|x2|v|x01|v|x10|}|x10|{|xr|}xs

По размеченному выражению составим отмеченную таблицу переходов.

yg

e

e

y3

e

e

e

e

y1

e

y1

e

e

e

e

0

1

2

3

4

5

6

7

8

9

1v3

3v6

3v8

*

X

1v3

1

1v3

3

3v6

3v8

6

1v3

8

1v3

1v3

3v6

3v8

*

X

4

*

4

4

4

4

*

4

*

4

4

4

4

*

X

5

*

5

5

5

5

*

5

*

5

5

5

5

*

X

2

2

2

*

7

9

7

2

9

2

2

7

9

*

При составлении таблицы следует учитывать, что для разных регулярных выражений автомат под действием одних и тех же входных сигналов переходит в разные состояния. Эти внутренние состояния будем отмечать множеством индексов основных мест. Например. В событии S3 переход из состояния 0 в состояние 1 происходит под действием сигнала x2 а в S1 под действием этого же сигнала из состояния 0 автомат переходит в состояние 3. Поэтому, внутреннее состояние, в которое автомат переходит под действием x2 из состояния 0, будем называть множеством из двух индексов 1 v 3. Аналогично получается переход из состояний 2, 7 и 9 под действием x2, а также переход из состояния 4 и 5 в состояния 3 v 6 и 3 v 8 соответственно под действием x2. При заполнении таблицы получается свободные клетки там, где переходы в автомате не определенны. Такие клетки будем отмечать звездочкой *, которую следует рассматривать как индекс некоторого внутреннего состояния. Таблица переходов составляется не только для состояний, отмеченных индексами основных мест регулярного выражения, но и для состояний, отмеченных множеством индексов. Для заполнения колонок для таких состояний достаточно образовать дизъюнкцию таких индексов, которые расположены в колонках, отмеченных индексами, входящими в множества. Например. Для заполнения колонки 1 v 3 образуем дизъюнкцию индексов расположенных в колонках 1 и 3. Поскольку состояния 1, 3, 6 и 8 отмечены пустой буквой e, то и состояния 1 v 3, 3 v 6, 3 v 8 также отмечаются буквой е.


 

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

84532. Потенціал дії атипових кардіоміоцитів сино-атріального вузла, механізми походження, фізіологічна роль 43.38 KB
  Така зміна стану каналів мембран АКМЦ веде до повільного зменшення мембранного потенціалу деполяризація мембрани. Частота з якою центр автоматії генерує ПД залежить від двох факторів: 1 величина порогового потенціалу; чим вона більша тим частота менша; в звичайних умовах під впливом механізмів регуляції частіше змінюється рівень мембранного потенціалу спокою зміна порогового потенціалу зміна частоти генерації імпульсів збудження водієм ритму зміна частоти серцевих скорочень; 2 швидкість повільної діастолічної деполяризації ПДД;...
84533. Провідна система серця. Послідовність і швидкість проведення збудження по серцю 42.64 KB
  Послідовність і швидкість проведення збудження по серцю. Швидкість проведення збудження по структурах серця різна. Чинниками що впливають на швидкість проведення збудження по мязовим волокнам є: діаметр волокон амплітуда ПД величина порогу деполяризації швидкість розвитку піку ПД наявність нексусів між міокардіоцитами вони мають низький опір що сприяє швидкій передачі ПД з одного КМЦ на другий і збільшенню швидкості проведення збудження. Причинами великої швидкості проведення збудження по провідній системі серця є: великий діаметр...
84534. Потенціал дії типових кардіоміоцитів шлуночків, механізми походження, фізіологічна роль. Співвідношення у часі ПД одиночного скороченння міокарда 51.9 KB
  Типові кардіоміоцити ТКМЦ не мають властивості автоматії і генерують ПД під впливом подразника ПД що йде від водія ритму серця. ПД в ТКМЦ має особливості а саме він дуже тривалий в шлуночках до 300 мс в нервових волокнах 1 мс в скелетних мязах 25 мс. Фази ПД ТКМЦ: 1. Повязана з виходом із ТКМЦ йонів калію та вхід хлору 3.
84535. Періоди рефрактерності під час розвитку ПД типових кардіоміоцитів, їх значення 40.19 KB
  Значення великої тривалості ПД ТКМЦ стає зрозумілим якщо співставити його в часі з графіком зміни збудливості ТКМЦ при збудженні з графіком поодинокого скорочення міокарда: ПД ТКМЦ тривалий через наявність фази плато. АР відповідає розвитку латентного періоду поодинокого мязевого скорочення періоду укорочення та значної частини періоду розслаблення. Завдяки такому співвідношенню у часі фаз збудливості та періодів поодинокого скорочення міокарда досягається: неможливість виникнення в міокарді тетанічних скорочень; наступний цикл...
84536. Спряження збудження і скорочення в міокарді. Механізми скорочення і розслаблення міокарду 44.46 KB
  Тобто ПД викликає скорочення таким чином: ПД поширюється по мембрані ТКМЦ в тому числі і по мембрані Ттрубочок відкриття кальцієвих каналів саркоплазматичного ретикулума СПР вихід йонів кальцію із СПР підвищення концентрації йонів кальцію в міоплазмі з 108 до 105 моль л дифузія йонів кальцію до скоротливих білків протофібрил взаємодія з регуляторними білками з тропоніном зміна третинної структури тропоніну та тропоміозину відкриття активних центрів актину взаємодія активних головок міозину з активними центрами актину...
84537. Векторна теорія формування ЕКГ. ЕКГ, відведення. Походження зубців, сегментів, інтервалів ЕКГ 42.75 KB
  ЕКГ відведення. Походження зубців сегментів інтервалів ЕКГ. Крива змін цієї різниці потенціалів в часі називається електрокардіограмою ЕКГ.
84538. Серцевий цикл, його фази, їх фізіологічна роль. Показники насосної функції серця і методи їх дослідження 58.82 KB
  Показники насосної функції серця і методи їх дослідження. Його будова повністю пристосована для виконання функцій насоса: СЕРЦЕ насос ШЛУНОЧКИ ПЕРЕДСЕРДЯ КЛАПАНИ Резервуарна функція Забезпечення одностороннього току крові Насосна функція ХОК який є адекватним потребам організму Таким чином насосну функцію виконують перш за все шлуночки серця. Серце як насос працює циклічно мають місце ритмічне чергування систоли скорочення та діастоли розслаблення відділів серця. Чергування систоли та діастоли різних відділів серця можна...
84539. Характеристика періодів і фаз СЦ 47.19 KB
  Починається скорочення передсердя з мязевих пучків які охоплюють гирла вен; це попереджує рух крові по градієнту тиску із передсердя в вени так як клапани тут відсутні. і внаслідок цього в шлуночок надходить остання порція крові яка складає від 8 до 30 від всього обєму крові що надходить в шлуночок при його діастолі. Тому напруження міокарду шлуночка і тиск в ньому не змінюється не відбувається рух крові через порожнини серця; не змінюється положення клапанів. В стані спокою в шлуночку знаходиться близько 150 мл крові.
84540. Показники насосної функції серця і методи іх дослідження 42.01 KB
  Цей показник можна визначити за допомогою ехокардіографії тетраполярної реографії не інвазивні методи за допомогою методу розведення барвника внутрішньовенно вводять певні барвники і по динаміці зміни її концентрації в крові розраховують ХОК а також за допомогою методу Фіка він заснований на визначенні хвилинного поглинання кисню організмом людини і на визначенні артеріовенозної різниці вмісту кисню; для визначення а в різниці необхідно провести зондування правого передсердя для отримання змішаної венозної крові; далі розрахунок...