6
$\begingroup$

Given a word $w$ and a language $L$, we want to check if $w\in L$. This is called the membership problem. Why is the membership problem important?

$\endgroup$
7
$\begingroup$

The importance is that any computational problem where the answer is yes or no can be phrased as a membership problem in a language. The language is the set of strings for which the answer is yes.

$\endgroup$
4
$\begingroup$

Suppose we show that a language $L$ belongs to some class $C$ of languages (say $L$ is regular). So what? Why would we bother showing that?

One reason is because we want to answer membership queries – given a word $x$, is it in $L$? For example, $L$ might be the context-free fragment of the syntax of a programming language, and we would like to be able to parse source code.

For an arbitrary language $L$, it is hopeless to answer the membership problem efficiently (or even at all). However, for some classes of languages, such as regular languages and context-free languages, efficient algorithms do exist. This is why these classes are important in the first place.

$\endgroup$
-1
$\begingroup$

What computation means to us today is that we write programs on the computer and finally run them.Now,the program is basically an algorithm that is implemented through a language,and there are a great many class of problems that do not allow algorithms to compute them or solve them.Now the set membership problem that we consider is carried upon sets of finite strings.when we write a program,the input is in the form of strings and output is also in the form of strings.So,if the set membership problem on the set of inputs and outputs allow algorithms to compute them then we say the program is capable to carry out its job else not.Hence the study of set membership problem on finite strings is a central problem in computer science.

$\endgroup$
1
  • $\begingroup$ I don't really understand what you mean by this answer. However, in computer science, computation does not mean writing and running programs. $\endgroup$ Mar 29 '18 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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