# Does B accepts the language L',no matter which is the initial automaton A?

#### evinda

##### Well-known member
MHB Site Helper
Hello!!!
I have a question..
Suppose that we have a finite automaton $A$(deterministic or not) and $L(A)$ the language that it accepts.It interest us to recognize the complement language $L'=(\Sigma^{*}-L(A))$.So,we reverse the states of A as followed:we make the accepting state non-accepting and the non-accepting,accepting,defining in that way a new automaton $B$.Does $B$ accepts the language $L'$,no matter which is the initial automaton $A$?If yes,prove it,else give a counter-example.

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Hello!!!
I have a question..
Suppose that we have a finite automaton $A$(deterministic or not) and $L(A)$ the language that it accepts.It interest us to recognize the complement language $L'=(\Sigma^{*}-L(A))$.So,we reverse the states of A as followed:we make the accepting state non-accepting and the non-accepting,accepting,defining in that way a new automaton $B$.Does $B$ accepts the language $L'$,no matter which is the initial automaton $A$?If yes,prove it,else give a counter-example.
Hey!!!

What is the simplest language you can think of that is not empty?

Then, what is the simplest complement language that you can think of, which is also not empty?

Does it fit?

#### evinda

##### Well-known member
MHB Site Helper
Hey!!!

What is the simplest language you can think of that is not empty?

Then, what is the simplest complement language that you can think of, which is also not empty?

Does it fit?
I don't really know..Could you give me a hint?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
I don't really know..Could you give me a hint?
Hmm, the simplest language defined by a finite automaton that is not empty...

... we need at least 1 input symbol, say $a$.
And we also need at least 1 state, say $S$.
And an initial state, which should be $S$ as well.
And at least 1 final state, which can be $S$ as well.
And at least 1 transition: say reading $a$ and making a transition from $S$ to $S$.

Which language does that generate?

#### Evgeny.Makarov

##### Well-known member
MHB Math Scholar
... we need at least 1 input symbol, say $a$.
And we also need at least 1 state, say $S$.
And an initial state, which should be $S$ as well.
And at least 1 final state, which can be $S$ as well.
And at least 1 transition: say reading $a$ and making a transition from $S$ to $S$.
And what is the point? The statement in post #1 is true for this automaton.

#### Klaas van Aarsen

##### MHB Seeker
Staff member
And what is the point? The statement in post #1 is true for this automaton.
Oh?

#### Evgeny.Makarov

##### Well-known member
MHB Math Scholar
... we need at least 1 input symbol, say $a$.
If the alphabet $\Sigma$ consists of $a$ only, then the language accepted by this automaton is the whole $\Sigma^*$. The accepted language of the automaton where this only state is not accepting is empty, as expected.

#### Klaas van Aarsen

##### MHB Seeker
Staff member
If the alphabet $\Sigma$ consists of $a$ only, then the language accepted by this automaton is the whole $\Sigma^*$. The accepted language of the automaton where this only state is not accepting is empty, as expected.
That would not be consistent with the other conditions I set.

#### Evgeny.Makarov

##### Well-known member
MHB Math Scholar
Could you say plainly what I am missing? I claim that if the single-state automaton you described is called $A$ and the corresponding automaton where the state is not accepting is called $A'$, then the language accepted by $A$ is $\{a\}^*$ and the language accepted by $A'$ is empty.

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Could you say plainly what I am missing? I claim that if the single-state automaton you described is called $A$ and the corresponding automaton where the state is not accepting is called $A'$, then the language accepted by $A$ is $\{a\}^*$ and the language accepted by $A'$ is empty.
Pick $\Sigma = \{a,b\}$.
That way $L'$ is not empty.

#### Evgeny.Makarov

##### Well-known member
MHB Math Scholar
Pick $\Sigma = \{a,b\}$.
That way $L'$ is not empty.
Ah, OK, so the statement in post #1 is true for deterministic automata. In particular, from each state there should be an outgoing arrow for each input symbol.

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Ah, OK, so the statement in post #1 is true for deterministic automata. In particular, from each state there should be an outgoing arrow for each input symbol.
... being explicit, the answer to the question in post #1 is no, the statement is not true.
Such a fine distinction.