# 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.

-

## migrated from cstheory.stackexchange.comJan 24 '13 at 11:35

This question came from our site for theoretical computer scientists and researchers in related fields.

This is a pretty standard exercise. What have you tried? Have you checked the usual references, e.g. textbooks? –  Raphael Jan 25 '13 at 11:32

## 1 Answer

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.

-