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

Undecidable Problem for Regular Languages

Submitted by: @import:stackexchange-cs··
0
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

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!

Context

StackExchange Computer Science Q#81542, answer score: 9

Revisions (0)

No revisions yet.