# Testing whether the language of one automaton is a subset of another

Is there an algorithm to solve following problem?

Given two finite automata $A$ and $B$. Determine whether the language recognized by automaton $A$ is a subset of language recognized by automaton $B$ or otherwise.

• This is a pretty standard exercise. What have you tried? Have you checked the usual references, e.g. textbooks? Commented Jan 25, 2013 at 11:32

Recall some closure properties of regular languages, namely that they are closed under complementation and intersection. Now, $L(A)\subseteq L(B)$ whenever $L(A)\cap\overline{L(B)}$ is empty. So you need to construct the automaton that accepts the intersection of $A$ and the complement of $B$ – these are standard constructions – and test whether the resulting automaton accepts the empty language. This can be checked by inspecting the automaton to see whether any accepting states are reachable from the initial state. If not, then the language accepted is empty.