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

1.1k questions

1.2k answers


543 users

+1 vote
Kindly redirect me to some sample Co-buchi to liveness and vice-versa examples other than the ones available in 2017 and 2018 question papers. Just to get a better understanding of the solution. Thank you.
in * TF "Emb. Sys. and Rob." by (350 points)
You can practice with any random automaton you can come up with. Any automaton can be interpreted as a Co-Büchi automaton.

Let's say you have an initial state q_0, a successor q_1, q_1 has two successors q_2 and q_2', q_0 is the successor of q_2 and q_2'. q_2' is not accepting, the others are accepting. It is a Co-Büchi automaton. wildly distribute transition labels over and convert it two liveness. Feel free to share your result.

1 Answer

+1 vote

Martin already gave the best advise: Use the online tool to generate a random automaton, interpret it as you like, and use the teaching tool to check the correctness of what you did. I am not aware of a book or internet page where you could find such examples. If someone finds some, please forward them here.

There is no need to have too many doubts about that, since there is always a simple way, where "simple" means that you don't need any creativity so solve the problem:

  1. If the automaton is given in a symbolic description, use the laws you find in the slides, e.g., 
    1. A∃(Q,I,R,FGφ) = A∃(Q,I,R,A∃({p},¬p,p→φ∧p′,Fp)) = A∃(Q∪{p},I⋀¬p,R⋀(p→φ∧p′),Fp).
    2. A∃(Q,I,R,Fφ) = A∃(Q,I,R,A∃({q},¬q,q′↔q∨φ,FGq)) = A∃(Q∪{q},I⋀¬q,R⋀(q′↔q∨φ),FGq)
    3. and so on.
  2. If the automaton is given explicitly, then read the comments that were already given in another answer, i.e., identify strongly connected components of accepting states, copy these, and make them the accepting ones. Also, understand what the above constructions do: For example, the first one starting with ¬p waits for the right point of time to switch to p where "right" means that from that point of time on always φ and thus p must hold. The same thought you have to apply on the explicit construction. 

And of course, there is the creative way that you often find in the example solutions. That is based on carefully analyzing the given automaton, understanding why it will accept which kinds of words, identifying this way the really important states, and then modifying that automaton based on these observations. That requires some experience, and to find good examples where you learn something from is not that simple. Random examples will typically not help that much here. I guess that is what you ask for. There is not that much that could be said here, but what you may check could be:

  • Which transitions are missing in the automaton (partial behavior)?
  • Which states have multiple transitions for an input (ambiguous behavior)?
  • Is there more than one initial state?
  • Does every word have a run? If not, which words are single out because of this?
  • Check strongly connected components for FG acceptance; and check just what is needed to reach the accepting states for an F-acceptance (what comes later doesn't matter anymore as long as there is still a run). 
  • Can you modify the set of accepting states without changing the transitions or the kind of acceptance condition? For example, for F-acceptance, every state that can only be reached through an F-state could also become one. For FG-acceptance, you can remove states that cannot be reached along a loop of FG-states, etc.
These "standard checks" often reveal some information you can exploit for a simpler construction, but  I am sure that the list could be continued. It may be worth to spend a few minutes to check whether there is a cheap way to solve the problem, but if you have doubts, simply apply the "simple" way above where you don't have to "think" too much about it. 
by (166k points)

Related questions

Imprint | Privacy Policy