5
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • $\begingroup$ Your statement "problems concerning regular languages" is not well-defined. The statement not the problems like "Is the language of a TM regular" does not help either. $\endgroup$ – fade2black Sep 22 '17 at 17:45
  • $\begingroup$ @fade2black Agreed, but not every question can be perfectly well-defined. I think this one's OK, even though there is scope for disagreement about whether any given answer really is valid. $\endgroup$ – David Richerby Sep 22 '17 at 17:48
  • $\begingroup$ Would PCP or transducer equivalence count? $\endgroup$ – Evil Sep 22 '17 at 17:57
8
$\begingroup$

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!

|cite|improve this answer
$\endgroup$
2
$\begingroup$

This answer might not be entirely to your taste because it uses Turing machines. I think it's a valid answer, since the input to the problem is a regular language, rather than a Turing machine.

Fix a universal Turing machine $U$ and consider the problem "Does $U(x)$ halt for every $x\in L$?" (or for some $x\in L$). For concreteness, we can represent $L$ itself by giving an encoding of a DFA that decides it.

It's easy to see that this language is undecidable: we can reduce the halting problem to it by translating the question "Does $M(w)$ halt?" into "Does $U(x)$ halt for every $x\in L$?", where $L = \{\langle M;w\rangle\}$. It's easy to translate a description of $M$ and $w$ into a description of a DFA that accepts only the string $\langle M;w\rangle$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I was also thinking of $\{\langle M \rangle \mid L(M) \in \mathrm{REG} \}$ for several classes of machines $M$, but those are more about those machines than regular languages, aren't they? $\endgroup$ – Raphael♦ Sep 23 '17 at 0:42
  • 1
    $\begingroup$ @Raphael Yeah, that's basically the problem forbidden in the question. $\endgroup$ – David Richerby Sep 23 '17 at 0:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.