I need quick help with quantifiers in this definition below

33 Views Asked by At

Given the transition relation $\delta \subseteq S \times \Sigma \times \Gamma \times S$, where the $S$'s are the source and target states respectively, while the $\Sigma$ is the set of input alphabet, and $\Gamma$ is the set of output alphabet. The definition that I want to write about state determinism which basically says that the state $q$ is considered to be deterministic if and only if for every input symbol there is only one output generated and one target state. I am writing down my definition, so please if it is wrong correct me.

$\forall a \in \Sigma,\forall c'\in \Gamma, \forall d'\in \Gamma, \forall r \in S, \forall r' \in S$ $if (q,a,c',r)\in \delta $ then $(q,a,d',r')\not \in \delta$. My concerns can we put it more simple as there are many "forall" . Another question are the cases of $r=r'$ or $c'=d'$ are covered in the "then" part or not as those cases are not deterministic.

1

There are 1 best solutions below

2
On

Your version never holds because of the equality cases. Instead, try: $$ \forall a \in \Sigma,\forall (c,d)\in \Gamma^2, \forall (r,s) \in S^2, [(q,a,c,r)\in \delta,(q,a,d,s)\in \delta]\implies (c,r)=(d,s) $$