Power automaton

A power automaton is a term used in theoretical computer science .

Power automata are used in particular as an aid to transform nondeterministic finite automata into deterministic finite automata . As a rule, power automata are not minimal, that is, they contain many redundant or unreachable states. They therefore usually form an intermediate step in the construction of deterministic finite automata.

definition

A finite automaton A is called a power automaton of the finite automaton B if its state set is just the power set of the state set of B. Expressed formally:

Let be the sets of states of automata A and B and let A be a power automaton of B. Then is . ${\displaystyle Z_{A},Z_{B}}$ ${\displaystyle Z_{A}={\mathcal {P}}(Z_{B})}$

See also

• Power set construction