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

Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
Sign up Log in
11 replies · 4K views
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.
 

Discussion

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