patternMinor
Translating non-deterministic finite automata with counters to deterministic ones
Viewed 0 times
translatingfinitecountersnonwithautomatadeterministicones
Problem
I know there are algorithms for translating regular NFAs into their corresponding DFAs. Can these algorithms be applied to automata that employ transitions involving counters in a straightforward way, or are there special considerations that need to be taken into account, or even different algorithms altogether?
Solution
Yes, they can be employed in a straightforward way. However, the size of the formulas blows up exponentially big.
Let $\ell_{s \to t}$ denote the formula on the NFA transition from $s$ to $t$. For instance, these formulas might look like $\text{ctr} \ge 3$ (require the counter to be at least 3, i.e., the transition is only active if the counter is at least 3) or $\text{ctr}' = \text{ctr}+1$ (update the counter by adding one to the counter, when the transition is followed). Let $Q$ denote the set of states of the NFA.
Then each state of the DFA will be a subset of $Q$. Also, the transitions are as follows: the formula on the transition from state $S$ to state $T$, where $S,T \subseteq Q$, is given by $\varphi_{S \to T}$, defined as
$$\varphi_{S \to T} := \bigwedge_{t \in T} \bigvee_{s \in S} \ell_{s \to t} \land \bigwedge_{s \in S} \bigwedge_{t' \notin T} \neg \ell_{s \to t'}.$$
Here, I adopt the convention that if there is no transition from $s$ to $t$ in the NFA, then we let $\ell_{s \to t}$ be the formula $\text{False}$.
The DFA's transitions will involve CNF formulas with literals $\ell$ given by formulas on the NFA transitions or their negations (i.e., conjunctions of clauses, where each clause is a disjunction of those $\ell$ formulas or their negation).
For instance, if the states of the NFA are $a,b,c,d$, then the DFA would have a transition from the state $\{a,b\}$ to the state $\{b,c\}$ with the formula
$$(\ell_{a \to b} \lor \ell_{b \to b}) \land (\ell_{a \to c} \lor \ell_{b \to c}) \land \neg \ell_{a \to a} \land \neg \ell_{a \to d} \land \neg \ell_{b \to a} \land \neg \ell_{b \to d}.$$
As an "optimization", you can test satisfiability of each formula $\varphi_{S \to T}$ and if it is not satisfiable, then exclude the transition $S \to T$ from the DFA.
We can compare to is determinism = non determinism for one counter automata?. Notice that the situation there is a bit different. One-counter automata allow only specific operations on the counter: increment, decrement, and test for zero. This limits the set of formula that can appear as $\ell$. Now, if we apply the above construction to a non-deterministic one-counter automaton, the formulas $\ell_{s \to t}$ for the NFA will be of this limited form ($\text{ctr'} = \text{ctr} + 1$, $\text{ctr'} = \text{ctr} - 1$, $\text{ctr'} = 0$, or $\text{ctr'} \ne 0$), but after we apply the above construction, we'll obtain a DFA where the transitions contain formulas that are much more complex. As a result, this does give a way to construct a DFA with formulas on the transitions, but the resulting DFA will not be a deterministic one-counter automaton, because its transitions are not limited to just increment, decrement, or test for zero. In other words: Can you determinize a NFA involving counters? Yes, if you allow the resulting DFA to have complex formulas in each transition (e.g., complex conditions on the counter), but not if you require the DFA to abide by the limitations associated with one-counter automata.
Let $\ell_{s \to t}$ denote the formula on the NFA transition from $s$ to $t$. For instance, these formulas might look like $\text{ctr} \ge 3$ (require the counter to be at least 3, i.e., the transition is only active if the counter is at least 3) or $\text{ctr}' = \text{ctr}+1$ (update the counter by adding one to the counter, when the transition is followed). Let $Q$ denote the set of states of the NFA.
Then each state of the DFA will be a subset of $Q$. Also, the transitions are as follows: the formula on the transition from state $S$ to state $T$, where $S,T \subseteq Q$, is given by $\varphi_{S \to T}$, defined as
$$\varphi_{S \to T} := \bigwedge_{t \in T} \bigvee_{s \in S} \ell_{s \to t} \land \bigwedge_{s \in S} \bigwedge_{t' \notin T} \neg \ell_{s \to t'}.$$
Here, I adopt the convention that if there is no transition from $s$ to $t$ in the NFA, then we let $\ell_{s \to t}$ be the formula $\text{False}$.
The DFA's transitions will involve CNF formulas with literals $\ell$ given by formulas on the NFA transitions or their negations (i.e., conjunctions of clauses, where each clause is a disjunction of those $\ell$ formulas or their negation).
For instance, if the states of the NFA are $a,b,c,d$, then the DFA would have a transition from the state $\{a,b\}$ to the state $\{b,c\}$ with the formula
$$(\ell_{a \to b} \lor \ell_{b \to b}) \land (\ell_{a \to c} \lor \ell_{b \to c}) \land \neg \ell_{a \to a} \land \neg \ell_{a \to d} \land \neg \ell_{b \to a} \land \neg \ell_{b \to d}.$$
As an "optimization", you can test satisfiability of each formula $\varphi_{S \to T}$ and if it is not satisfiable, then exclude the transition $S \to T$ from the DFA.
We can compare to is determinism = non determinism for one counter automata?. Notice that the situation there is a bit different. One-counter automata allow only specific operations on the counter: increment, decrement, and test for zero. This limits the set of formula that can appear as $\ell$. Now, if we apply the above construction to a non-deterministic one-counter automaton, the formulas $\ell_{s \to t}$ for the NFA will be of this limited form ($\text{ctr'} = \text{ctr} + 1$, $\text{ctr'} = \text{ctr} - 1$, $\text{ctr'} = 0$, or $\text{ctr'} \ne 0$), but after we apply the above construction, we'll obtain a DFA where the transitions contain formulas that are much more complex. As a result, this does give a way to construct a DFA with formulas on the transitions, but the resulting DFA will not be a deterministic one-counter automaton, because its transitions are not limited to just increment, decrement, or test for zero. In other words: Can you determinize a NFA involving counters? Yes, if you allow the resulting DFA to have complex formulas in each transition (e.g., complex conditions on the counter), but not if you require the DFA to abide by the limitations associated with one-counter automata.
Context
StackExchange Computer Science Q#161928, answer score: 3
Revisions (0)
No revisions yet.