Automata construction

In automata theory, automata construction is an important mathematical technique used to demonstrate the existence of an automaton with a certain desired property. Very often, it is presented as an algorithm that takes a desired property as input and produces as output an automaton with the property.

Many hard problems in automata theory involve finding the right construction of an automaton such that the problem can be answered. For example, the famous construction in McNaughton's Theorem answered the question if non-deterministic Büchi automaton can always be translated into a deterministic Muller automaton.

Example

Powerset construction is an algorithm to construct a deterministic finite automaton from a given nondeterministic finite automaton.

Optimality of a construction

An automata construction is called optimal if there is an input to the construction such that there exist no automaton that satisfy the desired property with smaller size complexity than output of the construction.

gollark: Observe, filtering.

gollark: I'm messing with image processing. By multiplying that mask with the (shifted) FFT of an image, I can effectively make a"low pass filter" thingy. I should probably find some actual educational material on this instead of just tweaking a badly written python program.

gollark: pls repost 849035452651536414

gollark: What? Unlikely, pyrobot.

gollark: If you *must* know, the noncognitohazard is just the inverse FFT of this thing shifted a bit.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.