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

[evinda]

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.

 

[I like Serena]

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]

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?

 

[I like Serena]

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]

... 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.

 

[I like Serena]

And what is the point? The statement in post #1 is true for this automaton.

Oh?

 

[Evgeny.Makarov]

... 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.

 

[I like Serena]

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]

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.

 

[I like Serena]

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]

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.

 

[I like Serena]

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.