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

Is it decidable if a language described by number of occurences is regular?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
numberdescribedregularoccurenceslanguagedecidable

Problem

It is known that the language of words containing equal number of 0 and 1 is not regular, while the language of words containing equal number of 001 and 100 is regular (see here).

Given two words $w_1,w_2$, is it decidable if the language of words containing equal number of $w_1$ and $w_2$ is regular?

Solution

I and several colleagues answered this question here with a necessary and sufficient criterion for when the language $L_{x=y}$ (all words having an equal number of occurrences of $x,y$) is regular. We also show the same for fewer $x$ than $y$, and more $x$ than $y$.

C.J. Colbourn, R.E. Dougherty, T.F. Lidbetter and J. Shallit.
Counting Subwords and Regular Languages.
Developments in Language Theory. DLT 2018. LNCS 11088. Springer. doi:10.1007/978-3-319-98654-8_19

Context

StackExchange Computer Science Q#12718, answer score: 5

Revisions (0)

No revisions yet.