Кіріспе
Автоматтар теориясындағы шекті күй машинасының түрі
Автоматтар теориясында шекті күй машинасы, егер оның әрбір өтуі бастапқы күйі және кіріс символы арқылы бірегей түрде анықталса, және әрбір күй өтуі үшін кіріс символын оқу қажет болса, детерминистік шекті автомат (DFA) деп аталады. Нендетерминистік шекті автомат (НФА) немесе нендетерминистік шекті күй машинасы осы шектеулерге бағынуға міндетті емес. Атап айтқанда, кез келген DFA сонымен қатар NFA болып табылады. Кейде NFA термині тар мағынада қолданылады, DFA емес NFA-ны білдіреді, бірақ бұл мақалада олай емес. Кіші жиын құру алгоритмін қолдану арқылы кез келген NFA-ны эквивалентті DFA-ға түрлендіруге болады; яғни, бірдей формальды тілді танитын DFA-ға. DFA сияқты, NFA да тек қана тұрақты тілдерді таниды. NFA 1959 жылы Майкл О. Рабин және Дана Скотт енгізген, сондай-ақ олардың DFA-ға эквивалентті екенін көрсеткен. NFA тұрақты өрнектерді жүзеге асыруда қолданылады: Томпсонның құрылымы – бұл тұрақты өрнекті NFA-ға компиляциялайтын алгоритм, ол жолдардағы үлгілерді тиімді түрде сәйкестендіре алады. Керісінше, Клейне алгоритмі NFA-ны тұрақты өрнекке түрлендіру үшін қолданылуы мүмкін (оның көлемі әдетте кіріс автоматтарында экспоненциалды болады). NFA көптеген жолдармен жалпыландырылды, мысалы, ε өтулері бар нендетерминистік шекті автоматтар, шекті күйдегі түрлендіргіштер, pushdown автоматтар, ауыспалы автоматтар, ω автоматтар және ықтималдық автоматтар. DFA-дан басқа, танымал NFA-ның арнайы жағдайлары – бірегей шекті автоматтар (UFA) және өзін-өзі тексеруші шекті автоматтар (SVFA).
each of its transitions is uniquely determined by its source state and input symbol, and
reading an input symbol is required for each state transition. A nondeterministic finite automaton (NFA), or nondeterministic finite state machine, does not need to obey these restrictions. In particular, every DFA is also an NFA. Sometimes the term NFA is used in a narrower sense, referring to an NFA that is not a DFA, but not in this article. Using the subset construction algorithm, each NFA can be translated to an equivalent DFA; i. e., a DFA recognizing the same formal language. Like DFAs, NFAs only recognize regular languages. NFAs were introduced in 1959 by Michael O. Rabin and Dana Scott, who also showed their equivalence to DFAs. NFAs are used in the implementation of regular expressions: Thompson's construction is an algorithm for compiling a regular expression to an NFA that can efficiently perform pattern matching on strings. Conversely, Kleene's algorithm can be used to convert an NFA into a regular expression (whose size is generally exponential in the input automaton). NFAs have been generalized in multiple ways, e. g., nondeterministic finite automata with ε moves, finite state transducers, pushdown automata, alternating automata, ω automata, and probabilistic automata. Besides the DFAs, other known special cases of NFAs
are unambiguous finite automata (UFA)
and self verifying finite automata (SVFA).
Бейресми таныстыру
NFA-ның мінез-құлқын сипаттаудың екі тәсілі бар, және екеуі де эквивалентті. Бірінші тәсіл NFA атауындағы белгісіздікті (nondeterminism) пайдаланады. Әрбір кіріс символы үшін, барлық кіріс символдары түгел пайдаланылғанға дейін NFA жаңа күйге өтеді. Әр қадамда автомат қолданылатын өтулердің біреуін белгісіздік бойынша "таңдайды". Егер кем дегенде бір "сәтті орындалу" (lucky run) болса, яғни кіріс толығымен пайдаланылғаннан кейін қабылдау күйіне жеткізетін таңдаулар тізбегі болса, кіріс қабылданады. Әйтпесе, яғни егер ешқандай таңдау тізбегі кірісті толығымен пайдалана алмай, қабылдау күйіне жеткізе алмаса, кіріс қабылданбайды. Екінші тәсілде NFA кіріс символдарының тізбесін бірінен соң бірін пайдаланады. Әр қадамда, егер екі немесе одан көп өтулер қолданылатын болса, ол өзін тиісті саны көшірмелерге "көшіріп алады", әрқайсысы әртүрлі өтуді орындап. Егер ешқандай өту қолданылмайтын болса, ағымдағы көшірме соқпаққа тіреліп, "қайтыс болады". Егер кіріс толығымен пайдаланылғаннан кейін көшірмелердің кез келгені қабылдау күйінде болса, кіріс қабылданады, әйтпесе қабылданбайды.
Ресми анықтама
Формалды анықтамаға толыққанды кіріспе үшін автоматтар теориясын қараңыз.
Күрделілігі
НФА үшін бослық мәселесін сызықтық уақытта шешуге болады, яғни берілген НФА тілі бос екенін тексеруге болады. Мұны істеу үшін бастапқы күйден тереңдікке іздеу жүргізіп, қандай да бір соңғы күйге жетуге болатынын тексеру жеткілікті. Бір НФА берілген кезде, оның барлық тізбектерді қабылдамайтынын, яғни әмбебап екенін тексеру PSPACE-ке толық. Соның салдарынан, кірістіру мәселесі де солай, яғни екі НФА берілгенде, біреуінің тілі екіншісінің тілінің ішкі жиыны болып табылады ма деп тексеру де PSPACE-ке толық. НФА A және бүтін сан n кіріс ретінде берілгенде, A-ның n ұзындығындағы қанша сөзді қабылдайтынын анықтау мәселесі шешілмейді; ол #P қиын. Шындығында, бұл мәселе SpanL күрделілік класы үшін толық (сақтықпен қысқартулар бойынша).
NFA-ны қолдану
NFA және DFA эквивалентті, яғни егер бір тіл NFA арқылы танылса, онда ол DFA арқылы да танылады, және керісінше. Мұндай эквиваленттілікті орнату маңызды және пайдалы. Бұл пайдалы, себебі берілген тілді тану үшін NFA құрастыру, сол тіл үшін DFA құрастыруға қарағанда кейде әлдеқайда оңайырақ болады. Бұл маңызды, өйткені NFA есептеу теориясындағы маңызды қасиеттерді анықтауға қажетті математикалық еңбектің күрделілігін азайтуға мүмкіндік береді. Мысалы, тұрақты тілдердің жабылу қасиеттерін NFA арқылы DFA-ға қарағанда оңайрақ дәлелдеуге болады.