0

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.

user440526
  • 1
  • Thanks for your answer. So As I understood the only way to exclude the equality cases is to use the pair notation. Is there any other ways without using pairs ??.

    Also to make sure that I got the correct output I will write down cases where I won't them to be excluded.

    let assume we have (q,a,b',r) as a valid transition. Are the following transitions are not accepted in the modified definition.? Because the target of my definition is to say all these cases are not valid.

    1.(q,a,b'',r).

    2.(q,a,b'',r').

    3.(q,a,b',r').

    Many thanks

     – user440526 May 31 '13 at 21:17

1 Answers1

0

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) $$

Did
  • 279,727
  • Thank you very much, but is there any way to avoid using the $S^2$ and $\Gamma^2$ and $\alpha^2$. and also if there is no transition defined from state q is the definition still holds. – user440526 May 31 '13 at 20:43
  • is there any way to avoid using the S2 and Γ2... What for? // and α2... Sorry? There is no $\alpha^2$ in the picture. // if there is no transition defined from state q is the definition still holds... Yes. – Did May 31 '13 at 23:19