Abstrakt. Vi visar att varje vanligt språk definierar en unik icke-deterministisk ändlig automaton (NFA), som vi kallar "átomaton", vars stater är "atomer" av språket, det vill säga icke-tomma korsningar av kompletterade eller okompletterade vänsterkvoter av språket. Vi beskriver metoder för att bygga átomaton, och bevisar att det är isomorphic till den normala automaton av Sengoku, och till en automaton av Matz och Potthoff. Vi studerar "atomiska" NFA: s där rätt språk i varje stat är en förening av atomer. Vi generaliserar Brzozuskis dubbel-reversal metod för att minimera en deterministisk finita automaton (DFA), visar att resultatet av att tillämpa undergruppskonstruktion till en NFA är en minimal DFA om och endast om motsatsen till NFA är atomär.
Brzozowski och Tamm REF visade att varje vanligt språk definierar en unik NFA, som de kallar átomaton.
Theory of Atomata
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}