Введение в теорию автоматов

автомат, не имеющий различных эквивалентных состояний.

автомат, не имеющий различных эквивалентных состояний.

способ задания автомата непосредственным определением функций ∘ ,∗.

Отображение f:A-> B называется гомоморфизмом полугруппы A в полугруппу B, если для любых a,b из A f(ab)=f(a)f(b).

Отображение f:A->A/θ полугрупп, при котором f (a)=aθ,  называется  естественным гомоморфизмом.

это пара множеств (V,E), где V - множество вершин, E - множество ребер, и каждому ребру e∈ E соответствует упорядоченная пара вершин (v,u), v,u ∈ E.

 способ задания автомата (с помощью ориентированного графа) состоит в следующем. Вершины - это состояния автомата. Из вершины a₁ выходит ребро с концом в a₂, если существует x ∈ X такой, что a₂=a₁ ∘ x. Это ребро обозначается парой (x,b), где  b - выходной символ, равный b=a₁∗ x.

Длиной слова x_i1x_i2 ... x_in  из X* называется число n. |t| - так обозначается длина t. По определению длина пустого слова равна нулю. 

Элемент e полугруппы A называется единицей, если для любого x из A ex=xe=x.