# Answer Set Programming for Regular Inference
## 3 Proposed Encoding for the Induction of NFA  
Our translation reduces NFA identification into an AnsProlog program. Suppose we are given a sample \(S\) over an alphabet \(\Sigma\), and a positive integer \(k\). We want to find a \(k\)-state NFA \(A=(\Sigma,\{q_{0},q_{1},\ldots,q_{k-1}\},q_{0},F,\delta)\) such that every \(w\in S_{+}\) is recognized by accepting and every \(w\in S_{-}\) is recognized by rejecting. The parameter \(k\) can be regarded as the degree of data generalization. The smallest \(k\), say \(k_{0}\), for which our logic program has an answer set, will give the most general automaton. As \(k\) increases, we obtain a set of nested languages, the largest for \(k_{0}\) and the smallest for some \(k_{m}\geq k_{0}\). Usually, the running time for \(k>k_{0}\) is shorter than for \(k_{0}\). Let \(\operatorname{Pref}(S)\) be the set of all prefixes of \(S_{+}\cup S_{-}\). The relationship between an automaton \(A\) and a sample \(S\) in terms of ASP is constrained as shown below in seven groups of rules. In rules (5)-(24) the following convention for naming variables is used: \(P\) stands for a prefix, \(N\) stands for a number (state index), \(I\), \(J\), and \(M\) also represent state indexes, \(C\) stands for a character (the element of alphabet), \(W\) stands for word (which is also a prefix), \(U\) represents another prefix. 1. We have the following domain specification, i.e., our AnsProlog facts. \[q(i)\leftarrow\.\quad\text{for all }i\in\{0,1,\ldots,k-1\}.\] (5) \[symbol(a)\leftarrow\.\quad\text{for all }a\in\Sigma.\] (6) \[prefix(p)\leftarrow\.\quad\text{for all }p\in\operatorname{ Pref}(S).\] (7) \[positive(s)\leftarrow\.\quad\text{for all }s\in S_{+}.\] (8) \[negative(s)\leftarrow\.\quad\text{for all }s\in S_{-}.\] (9) \[join(u,\,a,\,v)\leftarrow\.\quad\text{for all }u,v\in \operatorname{Pref}(S)\text{ and }a\in\Sigma\text{ such that }ua=v.\] (10) Facts (5) and (6) define the set of states \(Q\) and the input alphabet \(\Sigma\), while facts (7)-(9) describe the input sample. In particular, they define the prefixes as well as words to be recognized by accepting and rejecting, respectively. Finally, fact (10) defines the concatenation operation, which given prefix \(u\in\operatorname{Pref}(S)\) and symbol \(a\in\Sigma\) produces prefix \(v\in\operatorname{Pref}(S)\). 2. The next rules ensure that in an automaton \(A\) every prefix goes to at least one state and every state is final or not. \[x(P,\,N)\leftarrow\mathit{prefix}(P),q(N),\sim\mathit{ not\_x}(P,\,N).\] (11) \[not\_x(P,\,N)\leftarrow\mathit{prefix}(P),q(N),\sim x(P,\,N).\] (12) \[has\_state(P)\leftarrow\mathit{prefix}(P),q(N),x(P,\,N).\] (13) \[\leftarrow\mathit{prefix}(P),\sim\mathit{has\_state}(P).\] (14) \[symbol(a)\leftarrow\.\quad\text{for all }a\in\Sigma.\]0 (15) \[symbol(a)\leftarrow\.\quad\text{for all }a\in\Sigma.\]1 (16) Rules (11) and (12) describe the reachability of states \(q\in Q\) by prefixes \(p\in\operatorname{Pref}(S)\). State \(q\) is _reachable_ by prefix \(p\)_iff_ the prefix can be read by following a series of transitions from state \(q_{0}\) to state \(q\) (this series of transitions builds a _path_ for prefix \(p\)). The unreachable states are described by the default negation rule \(not\_x\). Clearly, for every prefix \(p\in\text{Pref}(S)\) and every state \(q\in Q\), either (11) or (12) holds. Here \(P\) (a prefix) and \(N\) (a number, state index) are variables, which means that during the grounding they will be substituted for, respectively, every \(p\in\text{Pref}(S)\) because of the atom \(prefix(P)\) in the body of the rule and for every \(i\in\{0,1,\ldots,k-1\}\) because of the atom \(q(N)\) in the body of the rule. Notice that for every \(p\in\text{Pref}(S)\) we already have fact \(prefix(p)\) and for every \(i\in\{0,1,\ldots,k-1\}\) we already have fact \(q(i)\), which are the sources of this substitution. Rules (13) and (14) declare that for every prefix \(p\in\text{Pref}(S)\) there has to be some reachable state \(q\in Q\).