1
$\begingroup$

So I'm kind of confused as I'm not that deep into the algebraic theory of languages.

The wikipedia article states:

Another way to state Schützenberger's theorem is that star-free languages and counter-free languages are the same thing.

What does counter-free languages mean here?

Let's say that $CL$ denotes the class of counter languages, i.e. the languages that a DFA emplyong one or more counters can accept [e.g. $(a^nb^{n+1})*$]. Clearly, for the class of regular languages $R \subset CL$.

Now I don't quite get what the class counter-free $CF$ is meant to represent here. Is it just the complement to counter-languages within the regular language class?

I.e. more precisely, my question would be:

$SF = CF \stackrel{?}{=} R \setminus CL$

This means: are regular languages either star-free or a counter language?

Thank you in advance!

Edit: Made things more clear

Edit 2: Ok the below resolved this

$SF = CF \neq R \setminus CL$

$\endgroup$
2
  • $\begingroup$ I am having difficulty understanding what your question is. I encourage you to refer to en.wikipedia.org/wiki/Aperiodic_finite_state_automaton, then edit your question to state clearly what your question is. I think you might find it a helpful exercise to link to or state what formal definition you are using for counter-free. $\endgroup$
    – D.W.
    Commented Nov 6, 2023 at 4:22
  • $\begingroup$ This is kind of part of my question. I don't understand what counter languages precisely are and how they can be regular. I'll edit my question to diffuse things a bit. $\endgroup$
    – Crea Teeth
    Commented Nov 6, 2023 at 22:23

1 Answer 1

2
$\begingroup$

These languages families are related by similar names only, both formalisms have their own relation to the concept of counting.

The beauty of regular languages is that they can be defined using (finite) automata, (regular) expressions and (monadic second order) logic. The Myhill-Nerode theorem shows that (minimal deterministic) automata are precisely equivalent to the algebraic syntactic monoid defined by the language.

Surprisingly (at least to me) there is a subfamily of the regular languages that has similar but restricted characterizations. Star-free languages are defined by operations (boolan operations and concatenation, no star). They can be characterized by either aperiodic syntactic monoids or first-order logic (Results by Schützenberger, McNaughton and Papert). The aperiodic monoid characterization can be rephrased as counter-free languages. In my intuition counter-free means we cannot hide a (modulo) counter inside the language: there is an integer $n$ such that for all words $x, y, z$ and integers $m \ge n$ we have $xy^mz \in L$ if and only if $xy^nz \in L$. https://en.wikipedia.org/wiki/Aperiodic_finite_state_automaton

The counter-automata start from pushdown automata with a single pushdown symbol (plus bottom-of-stack) which can basically only count up and down and check whether their counter equals zero. Thus one-counter languages are a subfamily of the context-free languages. It includes all regular languages. https://en.wikipedia.org/wiki/Counter_automaton

With two or more counters one can simulate a Turing machine by encoding the tape as a pair of numbers. This is nontrivial.

$\endgroup$
3
  • $\begingroup$ Yes, me again. I am not deep into algebraic language theory either, but I hope this helps. $\endgroup$ Commented Nov 6, 2023 at 22:32
  • $\begingroup$ Wasn't expecting anyone else :) $\endgroup$
    – Crea Teeth
    Commented Nov 6, 2023 at 23:35
  • $\begingroup$ I have also seen this definition (or the pumping lemma thereof) and It basically says that "nowhere in your string must language membership be dependent on you counting some parts of it". So I feel like there are some parallels to "real" counter languages somehow. Maybe it's just that counting in the regular language class is restricted to modulo counting. $\endgroup$
    – Crea Teeth
    Commented Nov 6, 2023 at 23:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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