Новости

Конечные распознающие автоматы. Процессоры

Работа добавлена:






Конечные распознающие автоматы. Процессоры на http://mirrorref.ru

2. Конечные распознающие автоматы. Процессоры.

1. Конечный распознаватель.

Конечный распознаватель – конечный автомат, в котором все множество состояний разделено на два класса: допускающие и недопускающие.

Конечный распознаватель процедур как правило не имеет.

Говорят, что входная цепочкаc=c0c1…cnраспознается (допускается)автоматомR, если автомат, начиная работу в начальном состоянии, под действием этой цепочки переходит в допускающее состояние.

В противном случае говорят, что цепочкаотвергается автоматомR.

Множество конечных цепочек, распознаваемое автоматомR, называетсярегулярным множеством автоматаR.

ПримерR1: Построим автомат, осуществляющий проверку на чётность во входной строке из единиц и нулей.

Входной алфавит:А={0,1}. Допускаем те цепочки, в которых четное число единиц.

Состояния:

s0 – прочитано 0 или четное число единиц (начальное, допускающее).

s1 – прочитано нечетное число единиц (недопускающее).

Допускающие состояния далее отмечаем единицей, а недопускающие – нулём.

0 1

Допустимость

s0

s0 s1

1

s1

s1 s0

0

Рассмотрим действие цепочек на этот автомат:

а)c=01011 Последовательность входных символов и состояний автомата можно изобразить следующей цепочкой.

нераспознается (так какS1 не допускающее состояние).

б)c=01010

– распознается (так какS0 допускающее).

в)c = ε — пустая цепочка, имеющая ноль символов (распознается).

ПримерR2: Пусть входной алфавитА={a,b}. Построим автомат, чтобы он распознавал только цепочки, где символa встречается парами: …aa …(или вовсе не встречается).

Состояния:

0 – не встречалось непарных символовa (допускающее, начальное).

1 – посл. символ – непарный а (недопускающее).

Е – ошибка, найдено непарное а (недопускющее).

a b

Допустимость

0

1 0

1

1

0 Е

0

Е

Е Е

0

Например цепочкаC =baab:  распознается;

С =aba:  не распознаётся.

Состояние ошибки – такое недопускающее состояние, которое сохраняется под действием всех символов входного алфавита.

ПримерR3: Пусть снова входной алфавитА={a,b}. Автомат допускает только цепочки, в которых встречается хотя бы одна пара символов: … аа …

Состояния:

1 – пара аа не найдена, предыдущий символb (или ε) (начальное, недопускающее).

2 – пара аа не найдена, предыдущий символ а (недопускающее).

F – пара аа найдена (допускающее).

a b

Допустимость

1

2 1

0

2

F 1

0

F

F F

1

Например, цепочкаC=aaa

автоматомR2:  — не распознается,

а автоматомR3:  — распознается.

2. Процессоры. На практике в программе, моделирующей работу конечного автомата, часто бывает необходимо “знать” момент окончания цепочки, чтобы провести завершение процедуры (например выдать на экран сообщение, что цепочка допускается или отвергается). Усовершенствуем определение автомата, введя в алфавит символ окончания строки: “┤”. При завершении работы автомата в допускющем состоянии вызовем процедуру «ДА», в недопускающем – «НЕТ».

Для преобразования управляющей таблицы автомата достаточно произвести два действия: стобец допустимости состояния заменить столбцом символа конца строки, допускающие состояния в нем (помеченные единицей) отметить процедурой «ДА», а недопускающие (помеченные нулём) процедурой «НЕТ».

0 1

s0

S0 s1

да

s1

S1 s0

нет

R1  R2 R3

a b

0

1 0

да

1

0 Е

нет

Е

Е Е

нет

a b

1

2 1

нет

2

F 1

нет

F

F F

да

Такой автомат называетсяпроцессором.

Редукция.

Ясно, что если автомат на некотором шаге попал в состояние ошибкиE, то нет смысла дочитывать до конца входную строку. Нужно просто переход в состояние ошибки заменить вызовом процедуры «НЕТ». Тоже можно сказать о переходе в состояниеF (find – найдено искомое), которой соответствует процедура «ДА».

Итак, переход в состояние Е заменяем на «НЕТ», а переход – вF заменяем вызовом процедуры «ДА», удаляя строку с соответствующим состояниемE илиF, поскольку теперь это состояние недостижимо.

R2 → редукцияR3 → редукция

a b

0

1 0

да

1

0нет

нет

а b

1

2 1

Нет

2

да1

Нет

Конечные распознающие автоматы. Процессоры на http://mirrorref.ru


Похожие рефераты, которые будут Вам интерестны.

1. Недетерминированые конечные распознающие автоматы

2. Конечные автоматы со стеком (Автоматы с магазинной памятью.) Вычисление выражений в польской записи

3. Праволинейные грамматики и конечные автоматы

4. Конечные автоматы и регулярные выражения

5. АВТОМАТИЧЕСКИЕ ВЫКЛЮЧАТЕЛИ (АВТОМАТЫ)

6. Текстовые процессоры

7. Табличные процессоры

8. Процессоры общие (центральные)

9. Excelкестелік процессоры. Күрделі өрнектерді есептеу. Крамер әдісі

10. Word текстік процессоры .Құжатқа суреттер, графиктік объектілер орнату