patternModerate
Given a language L what can we say about the decidability of whether this language is regular or not?
Viewed 0 times
thiscanthewhatsayregularlanguageaboutdecidabilitywhether
Problem
Can we develop a turing machine which on given a language L as input gives as output whether this language is regular or not?
Solution
As quicksort notes in his comment, languages are infinite objects and it is not possible to feed them to Turing Machines.
So we must be content to consider classes of languages for which there eists a finite description. We can for instance consider the context-free languages and give as input the grammar for the language.
Unfortunately, even for context-free grammars it is undecidable whether their language is regular.
Bar-Hillel, Perles, Shamir. On formal properties of
simple phrase structure grammars. (1961)
doi 10.1524/stuf.1961.14.14.143
So we must be content to consider classes of languages for which there eists a finite description. We can for instance consider the context-free languages and give as input the grammar for the language.
Unfortunately, even for context-free grammars it is undecidable whether their language is regular.
Bar-Hillel, Perles, Shamir. On formal properties of
simple phrase structure grammars. (1961)
doi 10.1524/stuf.1961.14.14.143
Context
StackExchange Computer Science Q#82932, answer score: 15
Revisions (0)
No revisions yet.