2
$\begingroup$

Is there any limit to what we can define as a language? Is any set of symbols a language?

For example, given the alphabet $\Sigma$, do we say that the language $L = \Sigma$ has alphabet $\Sigma$?

Also, what is the intuitive modern equivalent to languages (as defined WRT complexity classes)? I always hear languages described as problems, but what are we really saying when we say that a language is a problem?

$\endgroup$
6
$\begingroup$

Is there any limit to what we can define as a language?

No. Any set of strings over some alphabet is a language. Typically, in computer science, we're only interested in the case where the alphabet is finite and usually, though not always, we only consider finite strings, too.

Is any set of symbols a language?

A set of symbols is an alphabet. A language is a set of strings whose characters are in some alphabet, though you could also consider an alphabet to be a language of words of length 1..

For example, given the alphabet $\Sigma$, do we say that the language $L=\Sigma$ has alphabet $\Sigma$?

As above, yes.

Also, what is the intuitive modern equivalent to languages (as defined WRT complexity classes)?

A language is a language; the definition hasn't changed over time so I'm not sure what you mean by a "modern equivalent". A complexity class $C$ is a class of languages, classified by the amount of some resource (typically time or space) required to determine whether, for some $L\in C$, an input word is a member of $L$.

I always hear languages described as problems, but what are we really saying when we say that a language is a problem?

Languages and decision problems are essentially the same thing. Given a language $L$, the corresponding decision problem is "Given a word $w$, is $w\in L$?" More formally, a problem is a collection of objects of some kind (e.g., graphs or formlas) such as the 3-colourable graphs or satisfiable 3CNF formulas. A language then, is an encoding of the elements of a problem as strings, e.g., strings representing the adjacency matrices of 3-colourable graphs.

$\endgroup$
  • $\begingroup$ This is great! Is it the case then that the be-all and end-all of computation is the classification of all elements of a particular type? If we could construct all 3-colorable graphs, so that somewhere in some special computer we could store all 3-colorable graphs, and similarly all other problems of interest, and we could fetch them by identity, then would we be done? Is this what an oracle is? If this special computer existed for just 3-colorable-graphs, would this be an oracle for 3-colorable graphs? $\endgroup$ – baffld Mar 18 '14 at 4:05
  • $\begingroup$ I'm pretty sure an oracle is a computer that can't actually be built, but that has some way of "knowing" a given solution. I also wouldn't say it's the be-all and end-all. Very few practical problems are decision problems. More often than not, we're interested in a function, getting a result from a given input value. Decision problems are common because 1. they're easier to reason about and 2. so many of them are hard (either NP-hard or straight-up undecidable) that the corresponding function problems are necessarily intractable. $\endgroup$ – jmite Mar 18 '14 at 5:27
  • 1
    $\begingroup$ @baffld Yes, that would be exactly an oracle. But remember that there are infinitely many 3-colourable graphs so you can't just "construct all of them". $\endgroup$ – David Richerby Mar 18 '14 at 13:28

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.