В днешната технологична ера както хардуерът, така и софтуерът са забелязали огромно развитие. Една от основните области на развитие се наблюдава в методите на хардуерния дизайн. С нарастваща технология , беше възможно прилагането на концепцията за хардуер - съвместно проектиране на софтуер. Разработени са различни методи, чрез които, с помощта на софтуер човек може напълно да проектира и симулира хардуерните системи. Един от тези методи е теорията на автоматите. Теорията на автоматите е клонът на Информатика който се занимава с проектирането на абстрактния модел на изчислителните устройства, които следват автоматично предварително зададената последователност от стъпки. Тази статия разглежда кратка информация за ръководството за автомати.
Какво е теория на автоматите?
Думата Automata произлиза от гръцки, което означава „самодействащ се“. Automaton е математически модел на машината. Автоматът се състои от състояния и преходи. Тъй като входът се дава на автомат, той прави преход в следващото състояние, в зависимост от функцията на прехода. Входните данни за функцията за преход са текущо състояние и скорошни символи. Ако Автомат има краен брой състояния, той е известен като Краен автомат или Крайна държавна машина . Крайните автомати са представени от 5-кортеж (Q, ∑, δ, qo, F)
Където,
Q = Краен набор от състояния.
∑ = краен набор от символи, наричан още азбука на автоматите.
δ = преходната функция.
qo = начално състояние на входа.
F = набор от крайни състояния на Q.
Основни терминологии на теорията на автоматите
Някои от основните терминологии на теорията на автоматите са:
1 . Азбука : Всеки краен набор от символи в теорията на автоматите е известен като азбука. Представен с буквата∑ множеството {a, b, c, d, e,} се нарича азбучен набор, докато буквите от множеството „a“, „b“, „c“, „d“, „e“ се наричат символи.
две . Струна : В автоматите низът е крайна последователност от символи, взети от набора от азбуки ∑, Например низът S = ‘adeaddadc’ е валиден за набора от азбуки∑ = {a, b, c, d, e,}.
3 . Дължина на низа : Броят на символите, присъстващи в низа, е известен като Дължина на низа. За низа S = ‘adaada’ дължината на низа е | S | = 6. Ако дължината на низа е 0, тогава той се нарича празен низ.
4 . Kleen Star : Това е унарният оператор върху множеството символи Σ, който дава безкраен набор от всички възможни низове, включително λ, от всички възможни дължини над множеството Σ. Той се представлява от. Например за множеството Σ = {c, d}, ∑ * = {λ, c, d, cd, dc, cc, dd, ……}.
5 . Затваряне на Kleen : Това е безкрайният набор от всички възможни низове от набора от азбуки, с изключение на λ. Обозначава се с. За множеството Σ = {a, d}, ∑ + = {a, d, ad, da, aa, dd, ... ..}.
6 . Език : Езикът е подмножината на звездния набор Kleene∑ * за някакъв набор от азбуки Σ. Езикът може да бъде краен или безкраен. Например, ако езикът вземе всички възможни низове с дължина 2 над множеството Σ = {a, d}, тогава L = {aa, ad, da, dd}.
Официални езици и автомати
В теорията на автоматите, официалният език е набор от низове, където е всеки низ съставен от символи принадлежащи към крайния набор от азбуки Σ. Нека разгледаме котешки език, който може да съдържа всякакви низове от безкрайния набор по-долу ...
мяу!
ами
mewww !! ......
Азбуката, зададена за котешки език, е Σ = {m, e, w,!}. Нека този набор да се използва за модел на автомати от крайно състояние-m. Тогава официалният език, характеризиращ се с модела m, се обозначава с
L (m)
L (m) = {„мяу!“, „Меуу!“, „Меуууу“, ……}
Автоматът е полезен за дефиниране на език, защото може да изрази безкраен набор в затворена форма. Официалните езици не са същите като естествените езици, които говорим в ежедневието си. Официалният език може да обозначава различните състояния на машината, за разлика от нашите обикновени езици. Официалният език се използва за моделиране на част от естествения език, като синтаксис и т.н. ... Официалните езици се дефинират от автомати с краен режим. Има две основни перспективи на автоматите за крайни състояния - Акцептори, които могат да разберат дали низът е в езика, а втората е генераторът, който произвежда само низовете в езика.
Детерминистични крайни автомати
В детерминистичен тип автомати, когато се даде вход, винаги можем да определим в кое състояние ще бъде преходът. Тъй като това е краен автомат, той се нарича Детерминирани крайни автомати.
Графично представяне
Диаграма на състоянието е диграфите, използвани за графично представяне на детерминирани крайни автомати. Нека разберем с пример. Нека детерминираните крайни автомати бъдат ...
Q = {a, b, c, d}.
Σ = {0, 1}
= {a}
F = {d} а преходната функция бъде
Таблична форма на графично представяне
Диаграма на състоянието
Диаграма на състоянието на детерминистични автомати на крайното състояние
От диаграмата на състоянието
- Състоянията са представени с върхове.
- Преходите са представени от дъгата, обозначена с въведена азбука.
- Празната единична входяща дъга представлява началното състояние.
- Държавата с двойни кръгове е крайното състояние.
Недетерминирани крайни автомати
Автоматите, при които състоянието на изхода за даден вход не може да бъде определено, се наричат недетерминирани автомати. Нарича се още недетерминирани крайни автомати, тъй като има краен брой състояния. Недетерминираните крайни автомати се представят като набор от 5 - двойка, където (Q, ∑, δ, qo, F)
Q = краен набор от състояния.
∑ = Комплект азбука.
δ = преходната функция
където : 
qo = Първоначално състояние.
Графично представяне
Недетерминираните крайни автомати се представят с помощта на диаграмата на състоянието. Нека недетерминираните крайни автомати станат
Q = {a, b, c, d}
Σ = {0,1}
qo = {a}
F = {d}
Преходите са
Таблична форма на графично представяне
Диаграма на състоянието
Диаграма на състоянието на недетерминирани крайни автомати
Приложения за теория на автомати
Приложенията на теория на автомати включват следното.
- Теорията на автоматите е много полезна в областта на Теорията на изчисленията, компилаторни продукции, AI и др.
- За компилаторите за обработка на текст и хардуерните проекти крайните автомати играят основна роля.
- За приложения в AI и в програмни езици , Безконтекстната граматика е много полезна.
- В областта на биологията клетъчните автомати са полезни.
- На теория на крайните полета също можем да намерим приложението на автомати.
В тази статия научихме кратко въведение в езиците на теорията на автоматите и изчисленията. Автоматите съществуват от праисторическия период. С изобретяването на нови технологии се виждат много нови разработки в тази област. С какъв тип автомати сте се сблъсквали?
