A tutorial on finite automata
On language problems
A membership problem is the problem of deciding whether a word belongs to a language.
A decision problem D is defined by giving a set of instances, codified in a suitable way, and a question over it with yes or no answer.
Example
Given the following problem P:
Given an integer m, find the integer n such that n^2 = m
A decision problem D is:
Given two integers m and n, is m = n^2 ?
The language associated to a decision problem D is the set of strings that are images of instances with yes answer.
- Every problem
P can be transformed into a closely related decision problem D and viceversa the algorithm of the decision problem can be used to solve the original problem.
- We can then transform a decision problem
D in a membership problem: under a given representation r, an instance of a decision problem gives answer true iff its representation belongs to the language of yes instances of the problem D under r.
Back to Index