7. Автоматы распознавания языков icon

7. Автоматы распознавания языков



Название7. Автоматы распознавания языков
страница1/3
Дата конвертации01.09.2012
Размер0.63 Mb.
ТипДокументы
  1   2   3
1. /CA_Ant1/CA_ant04-25.doc
2. /CA_Ant1/CA_ant26-58.doc
3. /CA_Ant1/CA_ant_ОБЛОЖКА.doc
4. /CA_Ant1/CA_Аннотация.doc
5. /CA_Ant1/CA_БИБЛИОГРАФИЯ.doc
6. /CA_Ant1/CA_СОДЕРЖАНИЕ.doc
Введение
7. Автоматы распознавания языков
Антик м. И. Синхронные цифровые автоматы
Излагаются основы теории синхронных цифровых автоматов, способы их задания (описания), методы логического проектирования. Пособие состоит из 4 глав
Список гилл А. Введение в теорию конечных автоматов. М.: Наука, 1966
Содержание


––


7. Автоматы распознавания языков


Синхронный автомат (любой) можно рассматривать как устройство, распознающее некоторое множество Q слов конечной длины (само множество Q может быть бесконечным). Будем называть множество Q языком. Множество Q называют также событием - термином, который при проектировании может вызвать полезные ассоциации. Если во входной последовательности символов (букв) поступает слово, принадлежащее языку, то автомат выдает символ-индикатор этого языка.

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

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

Можно считать, что автономные автоматы способны распознавать слова только в однобуквенном алфавите. Распознаваемый автономным автоматом язык состоит из слов определенной длины.

7.1. Регулярные языки


Понятие “язык Q - регулярен” означает, что можно построить СЦА, распознающий язык Q.

Любое конечное множество слов конечной длины распознаваемо СЦА. В тоже время не всякий бесконечный язык регулярен, т.е. существуют языки, не распознаваемые СЦА. В некоторых случаях по описанию языка это свойство может быть установлено. Например, язык, состоящий из всех слов, в которых число нулей равно числу единиц, нерегулярен. Интуитивные соображения состоят в том, что автомат способен “считать” только до числа своих состояний, а поскольку число состояний автомата конечно, то он и не может распознать все слова из этого языка.
Но в общем случае задача установления регулярности языка алгоритмически не разрешима.

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

7.1.1. Инициальный конечный автомат с выделенным подмножеством выходных символов I.

В автоматном графе всем словам распознаваемого языка и только словам этого языка соответствуют пути от начала к вершинам или дугам, помеченным символами из множества I. В большинстве случаев можно считать, что множество выходных символов B={0,1}, а множество I={1}.

7.1.2. Источник - это ориентированный граф, у которого выделены начальные вершины и финальные вершины. Каждая дуга графа либо помечена символом алфавита А, либо непомечена.

Источник определяет регулярный язык Q над алфавитом А, порождаемый множеством всех путей из начальных вершин в финальные. Каждому такому пути соответствует слово, образованное символами алфавита А, являющихся пометками на дугах пути. Непомеченной (пустой) дуге соответствует пустой символ. Источник не содержит вершин, которые не достижимы из начальных, а также не содержит вершин, из которых недостижимы финальные.

Граф инициального автомата является источником, но, в общем случае, в источнике может быть нарушено условие однозначности автоматного графа, т.е. из одной вершины могут выходить несколько дуг, помеченных одинаково, выходить непомеченные дуги, вообще не выходить дуг (только для финальных вершин), может быть более одной начальной вершины. Источник, у которого нарушено условие однозначности, называют также недетерминированным конечным автоматом.

При выполнении вычислений синхронным автоматом может существовать только один последовательный процесс, каждому шагу (такту) которого соответствует только одна вершина автоматного графа. В источнике можно, в общем случае, считать, что либо существует одновременно (параллельно) более одного процесса аналогичного процессу над автоматным графом, либо существует один последовательный процесс, который в любом такте может находиться более чем в одной вершине источника. Источник всегда может быть преобразован (детерминизирован) в эквивалентный абстрактный автомат. Для этого все те вершины источника, которые в каком либо такте могли быть использованы одновременно, сопоставляются единственному состоянию автомата. Это можно сделать, если проследить все возможные варианты развития (прохождения) процессов в источнике. Алгоритм детерминизации см. ниже п.п.7.3.

7.1.3. Катенация (конкатенация) языков L1 и L2 определяется как язык L1_L2 = { qd, где q слово из L1, d слово из L2 }.

Катенация регулярных языков является регулярным языком. Пусть L = L1_L2, а Q1 и Q2 соответственно источники, представляющие эти языки. Тогда источник Q, представляющий язык L, строится следующим образом: начальные вершины источника Q совпадают с начальными вершинами источника Q1; финальные вершины источника Q совпадают с финальными вершинами источника Q2; все финальные вершины Q1 соединяются со всеми начальными вершинами Q2 (можно это сделать через одну новую вершину).

Итерация (или катенативное замыкание) языка L является множество L*, которому принадлежат все слова, являющиеся катенацией любого конечного числа слов из L, а также пустое слово.

Итерация регулярного языка L является регулярным языком L*. Если Q источник, представляющий язык L, то источник J, представляющий язык L*, строится следующим образом: все финальные вершины соединяются со всеми начальными вершинами дугами без меток, при этом все начальные и финальные вершины остаются теми же. Поэтому начальные вершины становятся также и финальными, и в языке появляется пустое слово.

7.1.4. Свойство быть регулярным множеством замкнуто относительно теоретико-множественных операций: объединения, пересечения, дополнения, разности, проекции, цилиндра.

1) Объединение. Пусть R1 и R2 регулярные множества, тогда объединение R = R1R2 также является регулярным множеством.

Если R1 и R2 представлены источниками, то источник, представляющий R, есть простое объединение этих источников такое, что множества начальных, финальных и промежуточных вершин являются объединением соответствующих вершин исходных источников с сохранением всех дуг без изменений.

Если R1 и R2 представлены инициальными автоматами с выходом B={0,1}, индикатором I={1}, то синхронная параллельная композиция этих автоматов с общим входом и объединением выходов по ИЛИ будет автоматом, представляющим искомый язык.

2) Пересечение. Если R1 и R2 регулярные множества, то пересечение этих множеств R = R1R2 также регулярное множество.

Если R1 и R2 представлены инициальными автоматами с выходом B={0,1}, индикатором I={1}, то синхронная параллельная композиция этих автоматов с общим входом и объединением выходов по И будет автоматом, представляющим искомый язык.

3) Дополнение. Если R язык над алфавитом А, то дополнение R является языком из множества А* всех слов в алфавите А, не принадлежащих языку R. Если R регулярное множество, то R также регулярное множество и может быть представлено автоматом с выходным алфавитом B={0,1}, индикатором I={1} и инверсным выходом.

4) Разность двух множеств R = R1\R2 = R1R2. Поэтому, если R1 и R2 регулярные множества, то регулярно также R = R1\R2.

5) Проекция. Для каждого слова в алфавите YZ с символами yzYZ его Y–проекцией называются слова с символами yY, т.е. стирается «лишний» компонент. Если алфавит YZ был входным алфавитом автомата, то будет нарушено условие автоматности графа, автомат становится недетерминированным, т.е. – источником.

6) Цилиндр. Если задан язык L над алфавитом Y, то Z-цилиндром языка называется язык над алфавитом YZ, Y-проекция которого принадлежат L. Если L регулярный язык, то его любой цилиндр также регулярный язык. Одним из «полезных» цилиндров является такой, в котором добавляемым компонентом является выходной алфавит автомата.

7.1.6. Дефинитный (определенный) язык может быть представлен как катенация А*_D, где А – входной алфавит, D – конечное множество слов ограниченной длины. Этот язык является бесконечным языком из слов, заканчивающихся словами из D.

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

Пример 7.1.-1. Спроектировать автомат, который устанавливает на выходе 1, если на двухразрядном входе автомата в последних 3-х тактах перед появлением кода 11 (в 4-м такте) появился только один раз код 00.

Введем, для удобства, следующие символы для обозначения комбинаций сигналов на входе автомата:



00



O

11



I

(01 или 10)



X

(I или X)



H


Автомат должен распознать в последовательности символов следующие слова: OHHI, HOHI, HHOI. Этим словам соответствуют следующие различные начала: , O, H, OH, HO, HH, OHH, HOH, HHO. Для построения автомата Мили достаточно каждому из этих начал сопоставить свое состояние. Для построения автомата Мура надо добавить еще состояния, соответствующие словам: OHHI, HOHI, HHOI. Пусть имена состояний автомата совпадают с началами слов, им сопоставленным. Тогда автомат Мура задается следующей автоматной таблицей:


сост.

вых.

O

X

I



0

O

H

H

O

0

O

OH

OH

H

0


HO

HH

HH

OH

0


HO

OHH

OHH

HO

0


O

HOH

HOH

HH

0


HHO

HH

HH

OHH

0


HHO

HH

OHHI

HOH

0


HO

OHH

HOHI

HHO

0


O

HOH

HHOI

OHHI

1


HHO

HH

HH

HOHI

1


HHO

HH

OHHI

HHOI

1


HO

OHH

HOHI



7.2. асинхронный язык.


В асинхронный язык входят слова, в которых “дли­тель­ность” любого из символов может быть произвольной. Точнее, если слово W принадлежит асинхронному языку, то в языке также содержатся все слова, полученные из W повторе­ниями любых букв из W либо вычеркиванием из W некоторых повторений отдельных букв.

Функция переходов автомата, определяющего асинхронный язык, имеет следующую особенность: для любого состояния s выполняется: если s:=g(z,a), то s:=g(s,a). Автомат может перейти в другое состояние только при изменении входного символа.

Назовем ядром асинхронного языка язык, в котором нет повторений символов. Асинхронный язык регулярен, если ядро этого языка – регулярное множество.

В частности, если ядро – дефинитный язык, то при синтезе автомата, распознающего асинхронный язык с таким ядром можно воспользоваться приемом из пункта 7.1.6.

При реализации автоматов, распознающих асинхронный язык, удобно использовать в кодах состояний коды входных символов, либо воспользоваться методом условной синхронизации (см.п.II.4), либо использовать то и другое.

Пример 7.2.-1. Спроектировать автомат с двухразрядным входом (in1,in2) и одноразрядным выходом, который индицирует следующее событие: после нулей на обеих линиях по каждой из линий in1 и in2 прошло ровно по одному блоку единиц любой длительности.

Решение будем искать в виде симметричной композиции двух одинаковых автоматов см. п.7.1.4.





Рис.7.2.-1. Композиция автоматов

Обозначим возможные символы (сочетания знач
ений сигналов) на входах автомата следующим образом:


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


a c a

a b q a

a b a q a




a c b a

a b c b a

a b c a

a b c q a

(Другой автомат распознает последовательности, полученные из указанных заменой b на q, q на b.)

Так же как в примере 7.1.-1, состояниям автомата сопоставим все различные начала распознаваемых слов. Эти же начала и будут именами состояний (столбец 1) в автоматной таблице 1.

Таблица 7.2.-1

1




2

3

4

имя




a

b

c

q



код






a







1

x10

a




S

ab

ac



2

a00

ab




aba

S

abc

abq

3

b00

ac

I,

a

acb

S



4

c00

aba




S

ab

ac

abaq

5

a01

acb

I,

a

S





6

b01

abc

I,

a

abcb

S

abcq

7

c01

abq

I,

a





S

8

q00

abaq

I,

a





S

8

q00

abcb

I,

a

S





6

b01

abcq

I,

a





S

8

q00


Комментарии к автоматной таблице. Буква S означает переход в то же состояние в силу асинхронности языка. Использование такого символа позволяет упростить процесс минимизации состояний автомата – (эквивалентные состояния выглядят как явно эквивалентные). Чтобы не загромождать таблицу, выходное значение обозначено только там, где должно индицироваться искомое событие. В столбце 3 строки-состояния перенумерованы так, что эквивалентные состояния имеют один и тот же номер. В столбце 4 код состояний выбран так, что бы два разряда кода формировались кодом символа, поступившим последним. Для состояния буква х означает любой символ кроме а.

Удалив эквивалентные состояния, получим автоматную таблицу 2 (состоянию соответствуют первые три строки таблицы).

Таблица 7.2.-2

код




a

b

c

q

b10




a00



c10

q10

c10




a00

b10



q10

q10




a00

b10

c10



a00






b00

c01

q10

b00




a01



c01

q00

c00

1,

a00

b01



q10

a01






b00

c00

q00

b01

1,

a00



c10

q10

c01

1,

a00

b01



q00

q00

1,

a00

b10

c10




Реализовать автомат можно в виде схемы рис.2. Контурная часть схемы идентична выше расположенным CL—RG с иным подключением входов:


A1  i2 B1  i4

A2  i1 B2  i3


Р
ис.7.2.-2. Реализация автомата

7.3. Детерминизация источника


Рассмотрим процедуру, позволяющую преобразовать источник в автомат Мура.

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

Действия:

1) Нумерация стрелок. Петли без меток из источника удаляются; каждая помеченная стрелка получает уникальный номер, начиная с 2 и далее 3,4,...

2) Таблица источника. Заготавливается таблица (пустая), в которой должны быть следующие столбцы: имена узлов, индексы узлов, остальные столбцы соответствуют всем символам входного алфавита.

3) Индексация узлов. Образуется новый единственный входной узел, который получает индекс 1. Этот узел соединяется стрелками без меток со всеми старыми входными узлами. Каждому узлу (за исключением узлов, из которых выходят только пустые стрелки) присваиваются уникальные имена, которые помещаются в таблицу. Узлам присваивается индекс, состоящий из номеров всех входящих в этот узел стрелок. Индекс узла, из которого выходит пустая стрелка, приписывается к индексу узла, в который эта стрелка входит. Индексы именованных узлов помещаются в таблицу.

4) В столбцы, именованные входными символами, записываются номера стрелок, выходящих из узла, соответствующего данной строке и данному входному символу.

5) Автоматная таблица. Заготавливается таблица (пустая), в которой должны быть следующие столбцы: шифр состояния, выходное значение, остальные столбцы соответствуют всем символам входного алфавита.

6) Заполнение строки автоматной таблицы. Первой строке, соответствующей начальному состоянию автомата, присваивается шифр 1. Начиная с этой строки, в столбцы, именованные входными символами, записываются номера стрелок, имеющих метку, совпадающую с именем столбца и выходящих из всех узлов, в индексах которых содержится какой-либо номер из шифра этого состояния (строки). Если таких стрелок нет, то записывается номер 0. В строке с шифром 0 во всех столбцах содержатся нули. (Состоянию с шифром 0 соответствует “тупиковое” состояние.)

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

8) Выходные значения. Выходным значением-индикатором помечается то состояние, в шифре которого есть номер, совпадающий с номером из индекса финального узла.

Пример 7.3.-1. Воспользуемся ранее рассмотренным примером. Спроектировать автомат, который устанавливает на выходе 1, если в последних 3-х тактах на двухразрядном входе автомата перед появлением кода 11 (в 4-м такте) появился только один раз код 00.

Введем следующие обозначения для сигналов на входе автомата:

00



O

11



I

(01,10)



X

Построим источник дефинитного языка (рис.1) и детерминизируем его.





Рис.7.3.-1 Источник дефинитного языка


Таблица источника:

имя

индекс

O

X

I

a

1,2,3,4

2

3

4

b

1,2,3,4

5

10,15

11,16

c1

5

--

6

7

c2

10,11

12

--

--

c3

15,16

--

17

18

d1

6,7

--

8

9

d2

12

--

13

14

d3

17,18

19

--

--

e

8,9,13,14,19

--

--

20

f

20

--

--

--


Таблица автомата:

шифр




O

X

I




1




2,5

3,10,15

4,11,16

A

2,5




2,5

3,10,15,6

4,11,16,7

B

3,10,15




2,5,12

3,10,15,17

4,11,16,18

C

4,11,16




2,5,12

3,10,15,17

4,11,16,18

C

3,10,15,6




2,5,12

3,10,15,17,8

4,11,16,18,9

D

4,11,16,7




2,5,12

3,10,15,17,8

4,11,16,18,9

D

2,5,12




2,5

3,10,15,6,13

4,11,16,7,14

E

3,10,15,17




2,5,12,19

3,10,15,17

4,11,16,18

F

4,11,16,18




2,5,12,19

3,10,15,17

4,11,16,18

F

3,10,15,17,8




2,5,12,19

3,10,15,17

4,11,16,18,20

G

4,11,16,18,9




2,5,12,19

3,10,15,17

4,11,16,18,20

G

3,10,15,6,13




2,5,12

3,10,15,17,8

4,11,16,18,9,20

H

4,11,16,7,14




2,5,12

3,10,15,17,8

4,11,16,18,9,20

H

2,5,12,19




2,5

3,10,15,17,8

4,11,16,7,14,20

J

4,11,16,18,20

1

2,5,12,19

3,10,15,17

4,11,16,18

FI

4,11,16,7,14,20

1

2,5,12

3,10,15,17,8

4,11,16,7,14,20

HI

4,11,16,18,9,20

1

2,5,12,19

3,10,15,17

4,11,16,18,20

GI


удаляя явно эквивалентные состояния, получаем автоматную таблицу, в последнем столбце которой приведены обозначения состояний из примера 7.1.-1.

Таблица 7.3.-1




O

X

I




A

B

C

C



B

B

D

D

O

C

E

F

F

H

D

E

G

G

OH

E

B

H

H

HO

F

J

F

F

HH

G

J

F

FI

OHH

H

E

G

GI

HOH

J

B

H

HI

HHO

FI,1

J

F

F

OHHI

HI,1

E

G

GI

HHOI

GI,1

J

F

FI

HOHI
  1   2   3



Похожие:

7. Автоматы распознавания языков iconАвтоматы: модель конечного автомата
«Автоматы: модель конечного автомата, распознаватели и преобразователи. Анализаторы контекстно-свободных языков»
7. Автоматы распознавания языков iconО настройке поведения взаимодействующих процессов
Ключевые слова: конечные автоматы, комбинаторные автоматы, полугруппы, комбинаторные моноиды
7. Автоматы распознавания языков iconГистограммный и полигональный способ оценивания плотности вероятности
...
7. Автоматы распознавания языков iconЭкономика природопользования
Автоматы в группе Стеценко А. В. получили те, чья команда выиграла, представляя задачу и те, кто из докладов подготовил ноосферу....
7. Автоматы распознавания языков iconДокументы
1. /СБИС для распознавания образов и обработки изображений. Пер. с англ. Под. ред. К. Фу. М....
7. Автоматы распознавания языков iconАнализ работы мо учителей иностранных языков за 2011-2012 учебный год
Работа мо учителей иностранных языков началась с изучения нормативных документов преподавания иностранных языков в 2011-2012 учебном...
7. Автоматы распознавания языков iconКабинет русского и иностранного языков для начальных классов
Выходной день (магнитный плакат с комплектом карточек для изучения ин языков – англ/нем)
7. Автоматы распознавания языков iconПрезентация магистерской диссертации Тема: Лингвокультурная общность русского и белорусского языков (концепт «еда»). Магистрант кафедры прикладной лингвистики
В условиях глобализации современного общества крайне важно выявлять механизмы лингвокультурной общности языков
7. Автоматы распознавания языков iconДокументы
1. /Коган кон. автоматы.doc
7. Автоматы распознавания языков iconФедеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования Владимирский государственный педагогический университет Факультет иностранных языков
Приглашаем принять участие в научно-практической конференции, которая состоится по случаю 45-летия факультета иностранных языков...
7. Автоматы распознавания языков iconДокументы
1. /МРБ-0537. Шумихин Ю.А. Телевизионные автоматы. (1964).djvu
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы