Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.3k answers

1.7k comments

556 users

0 votes
  • Eingabealphabet: Σ=Σ={{a},{}}
  • Zustandsvariablen: Vstate=Vstate={q0,q1}
  • Anfangsbedingung: φI=φI=q1&!q0|q0&q1
  • Akzeptanzbedingung: φF=φF=!q0&!q1|q0&!q1

the entry condition and acceptance condition can be simplified.

Initial condition: q1, 

Akzeptanzbedingung:!q1

how does s refer to?

I thought to do all with q1,so

  init 2;
accept 2?
But on the examples above, except init, everyone else is accept.
this is absolutely wrong.
How is it so 
 init 2,3?
in * TF "Emb. Sys. and Rob." by (190 points)

1 Answer

0 votes
I am not sure what you are really asking, but let me try to answer anyway. I understand that you refer to the Rabin/Scott construction discussed in https://q2a.cs.uni-kl.de/1137/sheet-9-exercise-rabin-scott-determinisation-not-accepted?show=1138#a1138 and you wonder how the initial states and accepting states are defined.

The initial state (it is only one in a deterministic automaton) is the set of initial states in the original automaton. The accepting states are those superstates which contain at least one accepting state of the original automaton.

In the mentioned example, the original automaton had initial states {s2,s3} so that is our new initial state (which was arbitrarily abbreviated as state Q0 of our deterministic automaton). The accepting states of the original automaton were {s0,s1}, and therefore states Q0:{s0;s2}, Q2:{s1}, Q4:{s1;s3} and Q5:{s0;s1;s2;s3} are the accepting states.

You further question is why we call the states s0,s1,s2,s3 instead of just 0,1,2,3 as in the text description and why they are called Q0,...,Q5 in the deterministic automaton. That is a matter of taste. The states could be given any names. In the images we add "s" or "Q" to avoid confusion in the discussions when we otherwise would just talk about state 2.
by (170k points)
In the mentioned example, the original automaton had initial states {s2,s3} ,
my question is actually where does this come from initial states {s2,s3} .
In Aufgabenstellung wird es nicht gegeben.
The problem described an automaton whose states are encoded symbolically with state variables q0 and q1 and inputs which are explicitly given as {a} and {} (which are to be read as two different input symbols).

With state variables q0 and q1, the automaton has the states s0:{}, s1:{q0}, s2:{q1} and s3:{s0,s1}. We understand these sets of state variables as variable assignments in that the state variables in the set are those made true while the rest of them is false.

Now, those state are initial states which satisfy the initial condition which is q1&!q0 | q0&q1 and these are the two states s2 and s3.

The accepting states are define in an analog way.
then it's extremely clear, thank you
Imprint | Privacy Policy
...