Новости

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

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






Конечные распознающие автоматы. Процессоры на 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. Реферат Процессоры общие (центральные)

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