Welcome to our community

Be a part of something great, join today!

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

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,723
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
Mar 5, 2012
8,854
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!!! :eek:

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
Apr 13, 2013
3,723
Hey!!! :eek:

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? :eek:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,854
I don't really know..Could you give me a hint? :eek:
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
Jan 30, 2012
2,502
... 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
Mar 5, 2012
8,854

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,502
... 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
Mar 5, 2012
8,854
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
Jan 30, 2012
2,502
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
Mar 5, 2012
8,854
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
Jan 30, 2012
2,502
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
Mar 5, 2012
8,854
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.