Алгебрична теория на автоматите
Посока в теорията на автоматите, характеризираща се с използването на алгебрични. средства при изучаването на автоматите. А. а. т. се основава на факта, че автоматите могат да се разглеждат като определени специални алгебри или алгебрични системи. В допълнение, събития, представени от крайни автомати, по отношение на операциите обединение, продукт и итерация, образуват алгебра, генерирана от краен набор от т.нар. елементарни събития, всяко от които се състои от една единствена буква или празна дума. Алгебричният подход ви позволява директно да използвате алгебричния. води до теорията на автоматите, а също така помага в някои случаи да се установи връзка между теорията на автоматите и други области на математиката. Така с помощта на теорията на автоматите бяха получени доказателства за разрешимостта на определени аритметични теории от втория етап, както и ново, по-просто решение на проблема, ограничен от Бърнсайд. От алгебричния от гледна точка автоматът (краен или безкраен) е триосновна алгебра, т.е. алгебра с три набора от елементи и две операции: X По този начин този подход ни позволява да асоциираме автомата с полугрупата от трансформации на множеството S с операцията на суперпозиция, генерирана от операциите a i , така че за произволни от A и s от S, тази полугрупа се нарича. автоматна полугрупа се използва като средство за описване на определени свойства на автоматите (класификация, разложимост, изоморфизъм и т.н.) върху алгебриката. език. В същото време всекиКъм полугрупа Q с единица може да се свърже автомат с дадена входна азбука и набор от състояния Q, както следва. Всяка буква от A е свързана с определен елемент и тогава преходната функция може да бъде дефинирана по следния начин: полугрупата на такъв автомат е изоморфна на подполугрупа на полугрупата, генерирана от елементите, и по този начин, ако генераторите на полугрупите са генератори на полугрупата, полугрупата на автомата е изоморфна на оригиналната полугрупа. Полугрупата на автомата очевидно е изоморфна на факторната полугрупа на входната полугрупа на всички думи в азбуката с операцията на последователно свързване на думи (конкатенация) чрез конгруентност.За произволно състояние конгруентността R е максималната субконгруентност на връзката.Това означава, по-специално, че събитието, представено от първоначалния акцептор, е обединението на някои R-класове. Тъй като полугрупата на автомата го характеризира до изоморфизъм, различните класове полугрупи съответстват на техните собствени класове автомати. В случай, когато полугрупата на автомата е свободна, или абелева, или циклична, или нилпотентна и т.н., или накрая група, автоматът се нарича съответно свободна, абелева, циклична, нилпотентна, група (или пермутабилна). Друг подход, свързан с алгебричния класификация на преходни и изходни функции, води до класове на линейни, заместващи и други автомати (вижте Автомат). Автоматите за заместване изпълняват функции едно към едно и се използват в теорията на кодирането. Линейните автомати представляват интерес поради простотата на тяхното схемно изпълнение. Автоматично име линеен автомат (l.a.), ако A, S и B са линейни пространства над някакво поле P, където са съответно линейни преобразувания: Обикновено се приема, че полето P е крайно, а пространствата A, S, B са крайномерни; в случая Л. А. екрайна машина. Ако при представянето на краен акцептор под формата на алгебра, чиито операции са буквите от входната азбука, позволяват многоместни операции, тогава полученото обобщение се нарича. автомат над термини (автомат над дървета, обобщен автомат). Такива автомати се използват за доказване на разрешимостта на определени математически проблеми. теории на втория етап.