patternMinor
Undecidable Problem for Regular Languages
Viewed 0 times
problemundecidablelanguagesregularfor
Problem
It might seems weird, but, Are there any undecidable problems concerning regular languages? I mean questions concerning the regular languages, not the problems like "Is the language of a TM regular?".
Clarification: By the questions regarding regular languages, I mean that the problem consists of regular languages, i.e. the relation between two or more regular languages, and/or about the properties of a regular language.
Thanks in advance
Clarification: By the questions regarding regular languages, I mean that the problem consists of regular languages, i.e. the relation between two or more regular languages, and/or about the properties of a regular language.
Thanks in advance
Solution
Yes, there are undecidable problems like the Post Correspondence Problem that can be coded into the language of a finite state automaton, as explained in my earlier answer to a (slightly broader) question: https://cs.stackexchange.com/a/6198
The result can be traced to a paper by Engelfriet and Rozenberg dealing with the so called twin shuffle operation.
Fixed Point Languages, Equality Languages, and Representation of
Recursively Enumerable Languages (J. ACM)
doi:10.1145/322203.322211
Recently Endrullis, Shallit and Smith presented the paper Undecidability and Finite Automata at the conference DLT2017 (doi:10.1007/978-3-319-62809-7_11, arxiv:1702.01394) which deals with your question:
Abstract. Using a novel rewriting problem, we show that several natural decision
problems about finite automata are undecidable (i.e., recursively
unsolvable). In contrast, we also prove three related problems are
decidable. We apply one result to prove the undecidability of a
related problem about k-automatic sets of rational numbers.
I am very proud that one of the references in this paper is to my earlier SE answer!
The result can be traced to a paper by Engelfriet and Rozenberg dealing with the so called twin shuffle operation.
Fixed Point Languages, Equality Languages, and Representation of
Recursively Enumerable Languages (J. ACM)
doi:10.1145/322203.322211
Recently Endrullis, Shallit and Smith presented the paper Undecidability and Finite Automata at the conference DLT2017 (doi:10.1007/978-3-319-62809-7_11, arxiv:1702.01394) which deals with your question:
Abstract. Using a novel rewriting problem, we show that several natural decision
problems about finite automata are undecidable (i.e., recursively
unsolvable). In contrast, we also prove three related problems are
decidable. We apply one result to prove the undecidability of a
related problem about k-automatic sets of rational numbers.
I am very proud that one of the references in this paper is to my earlier SE answer!
Context
StackExchange Computer Science Q#81542, answer score: 9
Revisions (0)
No revisions yet.