Definitions/Parallel Finite Automata
From The Perl Formal Language Toolkit
A Parallel Finite Automaton, as described by Stotts & Pugh, is equivalent to deterministic (DFA) and non-deterministic (NFA) finite automata.
Definition
A PFA is a 7-tuple, (N,Q,Σ,γ,δ,q0,F) such that:
- N - a finite set of nodes
- Q - a finite set of states, which consist of some set of nodes in N
- Σ - a finite alphabet
- γ - the nodal transition function
- δ - the state transition function
- q0 - the start state, which again may consist of some set of nodes in N
- F - the set of accepting states
PFAs may be expressed explicitly utilizing explicitly parallel regular expressions, which are like traditional regular expressions but with an additional shuffle or interleaving operator. This is also discussed in Stotts & Pugh.
Proof of Equivalence
Intuitively, a PFA may be modeled as two concurrently executing NFAs over a single string of symbols in Σ, and this string is only accepted as valid if it puts both NFAs into a final state once all symbols have been considered.
A new machine may be constructed for this argument.
Converting a PFA to NFA
An algorithm for converting a PFA to a NFA is presented in Estrade, et al. (PDF). This algorithm is implemented in this FLaT.
