Cheap and Secure Web Hosting Provider : See Now

[Answers] Limits to the definition of a language

, , No Comments
Problem Detail: 

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?

Asked By : baffld

Answered By : David Richerby

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22742

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback