logo
Теор

Введение. Виды автоматов.

  1. Т ривиальный автомат – это автомат без памяти. Zn = fZ ( xn )

  1. Конечный автомат. Z = F ( x, t )

  2. Б есконечный автомат (или машина Тьюринга).

  3. Л инейно-ограниченные автоматы (ЛО-автоматы).

  4. Автомат с магазинной памятью (МП-автомат).

Метод «черного ящика»:

нет необходимости разбивать систему на подсистемы, т.е.:

Z v = fZ ( xv , Sv )

S v+1 = fS ( xv , Sv )

У ступки:

  1. Б удем считать, что каждый раз мы будем рассматривать дискретную систему. Дискретная система действует в дискретные моменты времени. Дискретность выражается:

X = { 1, 2,… k }

Z = { 1, 2,… p }

S = { 1, 2,… l }

1, 2 – независимы. Дискретные системы, поведение которых не зависит от промежутка времени, между отдельными срабатываниями, называются синхронными системами. В отличие от тех, поведение которых зависит от этого промежутка и которые называются асинхронными системами.

  1. Будем рассматривать также конечную систему:

X = x1  x2  …  xk

Z = z1  z2  …  zp (декартово произведение)

Конечным автоматом называется дискретная синхронная система, с конечным входным алфавитом (X), конечным выходным алфавитом (Z), конечным множеством промежуточных состояний (S) и двумя характеристическими функциями (Zv, Sv + 1).