Определение автомата

Автомат – это кортеж <S, X, Y, d, λ, s₀, F>, где

S – множество состояний

X – алфавит входного языка

Y – алфавит выходного языка

d – функция перехода из состояния в состояние, зависящая от текущего состояния и входного символа

λ – функция вывода, зависящая от текущего состояния и входного символа, для автомата с выходом

s₀ – начальное состояние автомата

F – финальное множество состояний для распознающего автомата.

Классификация:

Конечный детерминированный Автомат Мили: совокупность пяти объектов A=(S, X, Y, d, λ), где S, X, Y – конечные непустые множества, а d, λ – отображения вида s(t+1) = d(s(t), x(t)) и y(t) = λ(s(t), x(t)), t принадлежит Т. Особенностью автомата Мили является то, что функция выходов является двухаргументной и символ в выходном канале y(t) обнаруживается только при наличии символа во входном канале x(t).

Конечный детерминированный Автомат Мура: совокупность пяти объектов A=(S, X, Y, d, λ), где S, X, Y и δ — соответствуют определению автомата типа Мили, а μ является отображением вида: μ: S → Y, с зависимостью состояний

y(t) = μ (s(t)), t принадлежит T. Особенностью автомата Мура является то, что символ y(t) в выходном канале существует все время, пока автомат находится в состоянии s(t).

Для любого автомата Мура существует автомат Мили, реализующий ту же самую функцию. И наоборот: для любого автомата Мили существует соответствующий автомат Мура.

Моделирование автоматов: Program Avtovat;

const

G: array[1..5,1..5] of Integer =

((2,3,4,5,1),

(3,4,5,0,2),

(4,2,1,2,3),

(5,1,2,0,4),

(2,0,5,1,4));

var

BeginState,CurState: Integer;

EndState: array[1..2] of Integer;

s: String;

i: Integer;

begin

Wrtiteln(‘Введите входную последовательнось:’);

Readln(s);

BeginState:= 1; // Начальное состояние

EndState[1]:= 4; EndState[2]:= 5; // Конечное состояние

writeln ('Входная последовательность: ',s);

CurState:= BeginState;

for i:= 1 to Length(s) do

begin

write ('Было ',CurState,' ');

CurState:= G[StrToInt(s[i]),CurState];

writeln('подано ',s[i],' Стало ',CurState);

if CurState = 0 then // 0 - переход невозможен

begin

writeln('Данная последовательность не принадлежит языку автомата');

Exit;

end;

end;

if CurState in [4..5] then

writeln('Данная последовательность принадлежит языку автомата')

else

writeln('Данная последовательность не принадлежит языку автомата');

end.

Минимизация автоматов:

Из 2-х детерминированных автоматов допускающих один и тот же язык меньше памяти при реализации занимает тот автомат, у которого меньше состояний. Число состояний автомата можно уменьшить, удалив те состояния, которые не используются при анализе допустимых цепочек. Автоматы упрощаются так:
1. Удаление недостижимых состояний.
2. Выявление эквивалентных состояний.
3. Выявление эквивалентных состояний.

Состояние qÎQ называется недостижимым, если под воздействием любого слова xÎS* автомат не переходит в состояние q

Состояние называется непродуктивным состояние qÎQ, для которого не существует xÎS* (q₀,x) вывод (q_n, x') нет вывода до финального состояния.

Слово x различает состояния q₁, q₂ из Q, если одно из этих состояний финальное, а другое не является финальным.

----------------------------------------------------------------------------------------------------------------

11) Информационно-обучающая система. Структура системы. Клиент серверная система. Язык HTML. Структура системы – тестирующей системы.

При автоматизированном обучении существует три категории пользователей:

1. администратор,

2. методист,

3. обучаемый.

В процессе обучения обучаемому предоставляется следующие возможности:

1. информационно-справочный методический материал, который может иметь текстовую, графическую, аудио-видео форму с элементами мультипликации, отображающие какие-то модели учебного материала;

2. упражнения-тренажеры, позволяющие учащемуся проверить понимание усвоенного материала;

3. тестирование, определяющее уровень знаний учащегося.

При подготовке тренажера необходимо в упражнениях учитывать усвоение определенных элементов учебного материала и предполагается повторное прохождение этих упражнений.

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

Это обеспечивается следующими принципами разработки тестов:

1. Большой базой задач,

2. Изменением порядка подачи задач датчиком случайных чисел,

3. при выборочном варианте ответов случайное смешивание порядка подачи вариантов ответов.

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

При разработке АОС (автоматизированной обучающей системы) возможно

1. Обучение на локальном компьютере. В этом случае АОС должна систему заданий держать в закодированной форме.

2. Обучение на локальной сети. В этом случае АОС должен находиться на сервере. И система контроля знаний должен проходить через серверный компьютер.

3. Обучение через интернет. В этом случае база данных АОС должна находиться на сервере, а на клиентском компьютере должна обеспечиваться система запросов на получение справочно-методического материала и текстов упражнений и тестов HTML средствами. Контроль же знаний должен обеспечиваться отсылкой ответов на сервер и проверкой его правильности там же. Если же этот процесс оставить на компьютере клиента, то есть возможность просмотра кода программы с текстом правильного ответа. Анализ ответа на сервере исключает такую возможность несанкционированного получения ответа.

Дата добавления: 2015-11-16