Во теоријата на информатиката, теоријата на автоматите ги проучува апстрактните машини и проблемите кои тие можат да ги решат.
Оваа статија можеби бара дополнително внимание за да ги исполни стандардите за квалитет на Википедија. Ве молиме подобрете ја оваа статија ако можете. |
Теоријата на автомати е тесноповрзана со теоријата на формални јазици поради тоа што автоматите честопати се класифицирани според класата на формални јазици кои тие можат да ги препознаат.
Автомат е математички модел на конечна машина (англиски: finite state machine - FSM). Конечна машина е машина која за даден почетен стринг преминува низ серија од состојби во зависност од преодните функции (кои можат да бидат претставени табеларно). Во т.н. Милеви машини (варијанта на конечна машина), овие преодни функции му кажуваат на автоматот на која состојба да оди во зависност од тековната состојба и тековниот симбол.
Влезот се чита симбол по симбол, сè додека не се прочита целосно (може да се замисли како лента на кои се испишани некои зборови, кои се читаа со помош на главата за читање од автоматот, главата се придвижува нанапред читајќи еден симбол при секое придвижување). Во оној момент кога влезниот стринг ќе биде прочитан целосно велиме дека автоматот треба да застане.
Во зависност од состојбата во која автоматот застанал, се вели дека автоматот го прифатил или отфрлил влезниот стринг. Ако автоматот застанал во состојба на прифаќање, тогаш автоматот го прифаќа зборот. Ако, од друга страна, главата застане во состојба на отфрлање, велиме дека зборот е отфрлен. Множеството на сите прифатени зборови од автоматот се нарекува јазик прифатен од автоматот.
Напомена. Автоматот не мора да има конечен број на состојби, или дури и преброив број на состојби. Така на пример, квантниот конечен автомат има непреброиво бесконечно состојби, како множество на сите можни состојби се јавува множеството од сите точки во комплексен проективен простор. Така, квантниот конечен автомат, исто како и конечните машини, се специјални случаи на една генерална идеја, идеја на тополошки автомати, каде состојбата ма состојби е тополошки простор а преодните функции се земаат од множеството на сите можни функции во тој простор. Тополошките автомати честопати се нарекуваат М-автомати, and are simply the augmentation of a semiautomaton with a set of accept states, where set intersection determines whether the initial state is accepted or rejected.
Општо земено, автоматот не мора строго да го прифаќа или отвфрла влезниот стринг, тој може да го прифати со одредена веројатност помеѓу нула и еден. Повторно ова е илсутрирано со квантен конечен автомат, која прифаќа влезни стрингови со одредена веројатност. Оваа идеја повторно е делл од една поопшта идеја, идејата за геометриски автомат или метрички автомат, каде што множеството на состојби се софпаѓа со одреден метрички простор, а јазикот е прифатен од автоматот ако растојанието помеѓу почетната точка и множеството на прифатени состојби е доволно мало во однос на метриката.
Автоматот се заснива на овие основни коцепти: симболи, зборови, азбуки и стрингови. These are
Автоматот е претставен од 5-tuple , каде:
Теорија на автоматите: формални јазици и формални граматики | |||
---|---|---|---|
Хиерархија на Чомски | Граматики | ||
Тип-0 | Неограничени | Рекурзивно преброиви | Тјурингова машина |
— | (нема вообичаено име) | Рекурзивни | Одлучувач |
Тип-1 | Контексно-осетливи | Контексно-осетливи | Линеарни |
— | Индексирани | Индексирани | Вгнезден склад |
Тип-2 | Контексно-слободни | Контексно-слободни | Недетерминистички потисни |
— | Детерминистички конт.-слоб. | Детерминистички конт.-слоб. | Детерминистички потисни |
Тип-3 | Регуларни | Регуларни | Конечен |
Секоја категорија на јазици или граматики е соодветно подмножество на категоријата над неа. |
This article uses material from the Wikipedia Македонски article Теорија на автоматите, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). Содржината е достапна под CC BY-SA 4.0 освен ако не е поинаку наведено. Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki Македонски (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.