5
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ This is a pretty standard exercise. What have you tried? Have you checked the usual references, e.g. textbooks? $\endgroup$
    – Raphael
    Commented Jan 25, 2013 at 11:32

1 Answer 1

Reset to default
12
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.