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

My questions:

1) How are we getting that both automatas in disjuntion are deterministic?

2) Aftergetting final automata how do we tell its deteministic or not?

 

in * TF "Vis. and Sci. Comp." by (870 points)

1 Answer

0 votes
As you know, automata are deterministic if every word has a unique run, and that is the case iff there is a unique initial state and for each reachable state and input letter, there is a unique successor state.

The mentioned automata are deterministic since they have a unique initial state (it is a minterm that assigns every state variable a unique value), and since the transition relation is  a conjunction of equivalences of the form next(q) <-> Phi(q,a), i.e., equivalences where the left hand side is a state variable and the right hand side is a formula without next-occurrences. Hence, whatever variable environment you have for the current state and input variables, the right hand side evaluates to either true or false and determines the value for next(q) uniquely. Since there is exactly one such equivalence for every state variable, the automata are deterministic.
by (170k points)

Related questions

0 votes
1 answer
0 votes
1 answer
0 votes
1 answer
0 votes
1 answer
asked Aug 11, 2020 in * TF "Intelligent Systems" by malaMahadevu (350 points)
Imprint | Privacy Policy
...