Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question

migrated from cstheory.stackexchange.com Jan 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 1

up vote 9 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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