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

AI Thread Summary
The discussion centers around the question of whether reversing the accepting and non-accepting states of a finite automaton A results in an automaton B that accepts the complement language L' of A, defined as L' = Σ* - L(A). Participants explore the implications of this transformation, particularly in the context of deterministic and non-deterministic automata. It is established that simply reversing the states does not guarantee that B will accept L', especially in cases where A accepts a non-empty language. A counter-example is provided: for a single-state automaton that accepts a language like {a}*, reversing the state leads to an automaton that accepts an empty language, demonstrating that the complement is not necessarily recognized by B. The conclusion drawn is that the initial statement is not universally true, particularly for non-deterministic automata.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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.
 
Technology news on Phys.org
evinda said:
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! :o

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 like Serena said:
Hey! :o

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? :o
 
evinda said:
I don't really know..Could you give me a hint? :o

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?
 
I like Serena said:
... 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.
 
Evgeny.Makarov said:
And what is the point? The statement in post #1 is true for this automaton.

Oh?
 
I like Serena said:
... 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.
 
Evgeny.Makarov said:
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.
 
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.
 
  • #10
Evgeny.Makarov said:
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.
 
  • #11
I like Serena said:
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.
 
  • #12
Evgeny.Makarov said:
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.
 
Back
Top