If you want to make money online : Register now

# [Solved]: Kripke automaton and observations

, ,
Problem Detail:

This is a question concerning Kripke automaton. My answers seem a little short and I was wondering if I was missing something? Transition table of a Kripke automaton:

A -> red light is on

B and D -> blue light is on

C -> both light are on

1) Is the test 001blue satisfied by any state?

``Attempt: No ``

2) Is the test 001red satisfied by every state?

``Attempt: Yes but I dont know how to show it. ``

3) Which test could tell difference btw A and C?

``Attempt: test = 100both; C satisfies test, A doesnt ``

4) Can any test distinguish B and C?

``Attempt: Yes, test = 10001blue; B satisfies test, C doesnt ``

5)Show that no test can tell the difference btw B and D.

``Attempt: Their observations are different. ``

Your answers seem correct. As for 2: one way is to simply check, a quicker way is to observe that all states go to A upon reading 1, so the sequence 001 ends in A, and A satisfies "red".

3 can be solved by the test "blue" (without any moves) and 4 can be solved with the test "red".

As for 5: in order to show that no test can differentiate B and D, observe that for the letter 1, both go to A, for the letter 0 both go to C, and both have the same light (blue). Thus, you can say that the "language" of both state is equal.