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

1k questions

1.2k answers


498 users

0 votes
February 17, 2021 - Problem 5a

a SU b = AE ({q}, ¬q, ¬q & a & ¬b & ¬q' | (q | b) & q' , Fq)

Can you explain how to write this transition relation
in # Study-Organisation (Master) by (850 points)

1 Answer

0 votes

Well, there are many ways how to solve that exercise. The task was to generate an automaton that is equivalent to [a SU b] with an acceptance condition of the form Fq. Following the semantics of [a SU b], it holds if there is a point of time where b holds and until then a must hold. Thus, we may start in a state {} with a self-loop for a&!b and a transition to state {q} when b holds. Clearly, we have to reach state {q}. There is no transition for !a&!b in state {} since then [a SU b] would be false, so that transition is missing intentionally. Once reached state {q}, nothing else has to be demanded, but we must consume further inputs which are don't cares. Hence, there is a self-loop on {q} for any input.

We can now write down the transitions as single midterms

  • ¬q & a & ¬b & ¬q'
  • ¬q & b & q'
  • q & q'
The disjunction of these yields the above transition relation. 
by (162k points)
Imprint | Privacy Policy