Нека A=(Q,R,S,T) е краен e-автомат над S. В такъв случай елементите на множествата Q, R, S и T се наричат съответно състояния, преходи, начални състояния и заключителни състояния на A, като тройките от R с втора компонента e се наричат e-преходи на A. В частния случай, когато множеството на e-преходите на A е празно, казваме, че A е краен автомат над S. Граф на A наричаме наредената четворка (Q,R,a,b), където a и b са функциите, съпоставящи на всяка тройка от R съответно нейната първа и нейната трета компонента. Ако D е път в графа на A, то конкатенацията на вторите компоненти на последователните ребра в D ще наричаме дума, съответна на D. Ако q и qў са две състояния на A, а w е дума над S, казваме, че qў е w-достижимо в A от q, ако думата w е съответна на някой път от q до qў в графа на A. Казваме, че дадена дума w над азбуката S се приема от A, ако някое заключително състояние на A е w-достижимо в A от някое начално състояние на A. Език на A наричаме множеството на онези думи над S, които се приемат от A.

      Два крайни e-автомата над S наричаме еквивалентни, ако техните езици съвпадат.

      Теорема 1. Всеки краен e-автомат над S е еквивалентен на някой краен автомат над S със същия брой състояния.

      Доказателство. Нека A=(Q,R,S,T) е краен e-автомат над S. Да означим с R° множеството на онези тройки (q,s,r) от QґSґQ, за които съществува такова състояние qў на A, че тройката (qў,s,r) принадлежи на R и qў е e-достижимо в A от q. Нека T° е множеството на онези състояния на A, от които в A е e-достижимо някое заключително състояние на A. Тогава четворката (Q,R°,S,T°) е краен автомат над S, еквиалентен на A.

      Един език над S се нарича автоматен, ако е език на някой краен автомат над S. От горната теорема следва, че езикът на всеки краен e-автомат над S е автоматен.

 Последно изменение: 1.12.2001 г.