Skip to main content
added 72 characters in body
Source Link

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$

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

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$

added 312 characters in body
Source Link

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

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 seem to be just$R \subset CL$.

Now I don't quite get what the same asclass counter-free languages$CF$ is meant to represent here. Is this the same asit just the complement ofto counter-languages (withinwithin the regular languages)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?

Here, counter languages do not seem to be the languages that can only be accepted by a k-counter automaton, as that would render them non-regular, I suppose? I guess I'm just really confused what defines counter languages then?

Thank you in advance!

Edit: Made things more clear

So I'm kind of confused as I'm not that deep into the algebraic theory of languages. I've seen that star-free regular languages seem to be just the same as counter-free languages. Is this the same as the complement of counter-languages (within the regular languages)? I.e. are regular languages either star-free or a counter language?

Here, counter languages do not seem to be the languages that can only be accepted by a k-counter automaton, as that would render them non-regular, I suppose? I guess I'm just really confused what defines counter languages then?

Thank you in advance!

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

Source Link

Is the class of star-free languages just the complement to counter languages within the regular language class?

So I'm kind of confused as I'm not that deep into the algebraic theory of languages. I've seen that star-free regular languages seem to be just the same as counter-free languages. Is this the same as the complement of counter-languages (within the regular languages)? I.e. are regular languages either star-free or a counter language?

Here, counter languages do not seem to be the languages that can only be accepted by a k-counter automaton, as that would render them non-regular, I suppose? I guess I'm just really confused what defines counter languages then?

Thank you in advance!