HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Why is the set for which a decision problem is true called a "language"?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
problemwhythecalledtruelanguagedecisionforwhichset

Problem

When we have a decision problem, " does $f(x)=1$ hold?", we call the set of strings $x$ for which the answer is yes a "language".

Why this strange terminology?

Solution

I believe a lot of this came out of linguistics research. People wanted to write down a formal description (grammar) of, e.g., the English language. By extension, the set of strings defined by any grammar is a language and, since unrestricted grammars are Turing-powerful, any computable set of strings is the language of some grammar.

Context

StackExchange Computer Science Q#89419, answer score: 14

Revisions (0)

No revisions yet.