patternModerate
Why is the set for which a decision problem is true called a "language"?
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?
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.