<p>$M_C$ must accept every word of $S^+ = B$ and reject every word of $S^- = A \setminus B$.</p>

<p>Let $A$ and $B$ be finite and such that both $S^+$ and $S^-$ are non-empty. Then exact computation of $M_C$ is NP-hard. [1]</p>

<p>[1] E.M. Gold. Complexity of Automaton Identification from Given Data. <em>Information and Control</em>, 37, 302-320 (1978)</p>

CC BY-SA 4.0
2018-05-15T11:40:25.363Z
2018-05-15T11:40:25.363Z
Dmitri Urbanowicz
<p>Suppose I have regular languages $B \subseteq A$, with corresponding (known) minimal deterministic finite automata $M_A, M_B$.</p>

<p>I would like to find another regular language $C$ such that $B = A \cap C$ that minimizes the size of $M_C$ (the minimal DFA corresponding to $C$).</p>

<p>In general $M_C$ can be much smaller than $M_B$. e.g. if we let $B$ the set of strings in $A$ that have even length, $M_C$ can be a two-state machine, while $M_B$ may be about as complex (or more) as $M_A$.</p>

<p>This feels like it should be an easy application of existing automaton minimization algorithms, but I'm not seeing it if so.</p>

<p>What looked liked the obvious thing to try to do is to to try and distinguish strings using an analogue of the Myhill-Nerode theorem, with the distinguishing relationship being that $x, y$ are distinct if there is some $s$ such that $xs, ys \in A$ but $xs \in B \neq ys \in B$, but the problem is that the corresponding indistinguishability relation is no longer transitive (I think) - Given $a$ indistinguishable from $b$ indistinguishable from $c$, there might be $s$ such that $as, cs \in A$ with $as \in B \neq cs \in B$, but $bs \not\in A$, so $s$ cannot be used to distinguish $a$ from $c$.</p>

<p>I think this arises from some genuine ambiguity in the problem - unlike normal DFA minimization, there's no reason to expect $M_C$ to be unique - two non-equivalent machines could represent languages $C \neq C'$ such that $A \cap C = A \cap C'$. It might be that those ambiguities don't matter and you can just resolve them arbitrarily, but I haven't been able to convince myself of that.</p>

<p>The problem is at least "reasonably tractable", as the corresponding decision problem is in NP, because such an automaton has size at most $|M_B|$, and we can determine whether a given automaton is a solution by testing its equivalence with the intersection automaton with states $M_A \times M_B$, and testing equivalence is in $P$. There's almost certainly some nice transformation into SAT or ILP that I haven't worked through yet because I'm hoping for a better solution.</p>

<p>Is this some well studied problem? Or can it be reduced to one?</p>

CC BY-SA 4.0
2018-05-15T11:40:32.740Z
This has been asked and answered here:https://cs.stackexchange.com/questions/64234/determining-a-minimal-state-regular-language-a-such-that-a-cap-b-c-given
Shaull
<fl.formal-languages><automata-theory><regular-language><minimization>
Finding a minimal DFA whose language has a desired intersection with another
DRMacIver
# Finding a minimal DFA whose language has a desired intersection with another

(Asked by: username_0 on 2018-05-15)

Suppose I have regular languages $B \subseteq A$, with corresponding (known) minimal deterministic finite automata $M\_A, M\_B$.

I would like to find another regular language $C$ such that $B = A \cap C$ that minimizes the size of $M\_C$ (the minimal DFA corresponding to $C$).

In general $M\_C$ can be much smaller than $M\_B$. e.g. if we let $B$ the set of strings in $A$ that have even length, $M\_C$ can be a two-state machine, while $M\_B$ may be about as complex (or more) as $M\_A$.

This feels like it should be an easy application of existing automaton minimization algorithms, but I'm not seeing it if so.

What looked liked the obvious thing to try to do is to to try and distinguish strings using an analogue of the Myhill-Nerode theorem, with the distinguishing relationship being that $x, y$ are distinct if there is some $s$ such that $xs, ys \in A$ but $xs \in B \neq ys \in B$, but the problem is that the corresponding indistinguishability relation is no longer transitive (I think) - Given $a$ indistinguishable from $b$ indistinguishable from $c$, there might be $s$ such that $as, cs \in A$ with $as \in B \neq cs \in B$, but $bs \not\in A$, so $s$ cannot be used to distinguish $a$ from $c$.

I think this arises from some genuine ambiguity in the problem - unlike normal DFA minimization, there's no reason to expect $M\_C$ to be unique - two non-equivalent machines could represent languages $C \neq C'$ such that $A \cap C = A \cap C'$. It might be that those ambiguities don't matter and you can just resolve them arbitrarily, but I haven't been able to convince myself of that.

The problem is at least "reasonably tractable", as the corresponding decision problem is in NP, because such an automaton has size at most $|M\_B|$, and we can determine whether a given automaton is a solution by testing its equivalence with the intersection automaton with states $M\_A \times M\_B$, and testing equivalence is in $P$. There's almost certainly some nice transformation into SAT or ILP that I haven't worked through yet because I'm hoping for a better solution.

Is this some well studied problem? Or can it be reduced to one?

**Tags:** fl.formal-languages, automata-theory, regular-language, minimization

> **Comments:**
> **username_1**: This has been asked and answered here:https://cs.stackexchange.com/questions/64234/determining-a-minimal-state-regular-language-a-such-that-a-cap-b-c-given  

---

## 1 answers

### Answer by username_2 on 2018-05-15. Score: 9 | Accepted answer

$M\_C$ must accept every word of $S^+ = B$ and reject every word of $S^- = A \setminus B$.

Let $A$ and $B$ be finite and such that both $S^+$ and $S^-$ are non-empty. Then exact computation of $M\_C$ is NP-hard. [1]

[1] E.M. Gold. Complexity of Automaton Identification from Given Data. *Information and Control*, 37, 302-320 (1978)


---

