I'm a student of Formal Methods in Software Engineering, I'm trying to study this question for two days but still haven't figured it out, I couldn't even find a similar solution or explanation, so please if anyone can explain in detail the question and it's solution I've provided in the image, it'll be a real help. One last thing, my guess is that the solution provided in the image is not correct, or maybe its my logic that isn't, so please help me with this. Thank You.
-
$\begingroup$ If I understand the provided diagram, after the four inputs 0011, the emitted output is 0000 upon reaching state s4 instead of the expected 0001 $\endgroup$– TarikFeb 26, 2018 at 17:11
-
$\begingroup$ Do you have any specific question about the exercise? "Please explain this question and solution" isn't a good fit here, as it's not clear what exactly you are stuck on, what you are confused about, or why you think the answer is incorrect. $\endgroup$– D.W. ♦Feb 26, 2018 at 18:21
-
$\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$– D.W. ♦Feb 26, 2018 at 18:21
-
$\begingroup$ @D.W. The diagram seems wrong. The O.P. is asking if it is correct or not. Finally, are you saying that images are prohibited on this site? $\endgroup$– TarikFeb 26, 2018 at 18:37
-
$\begingroup$ @Tarik, if their question is "Is the diagram correct?" and the post were edited to ask that question explicitly (and only that question), that would be specific enough and would address the concerns about being unclear. Would you like to take a try at suggesting an edit to that effect? $\endgroup$– D.W. ♦Feb 26, 2018 at 19:05
1 Answer
- Create a FSA that falls on the same state at the end of a 100 sequence.
- Create a second independent FSA that falls on the same state upon the end of 011 sequence.
- Now feed a zero to both FSAs at the same time and take note of the pair of states reached. Now go back and feed a 1 and take note of the pair of states reached, and so on. You will end up with a new FSA made up of pairs of states belonging to the Cartesian product of the set of states of the first and second FSA.
- The output at the transition between two pairs of states is the logical OR of the outputs of the original FSAs.
In fact, you can also build a non deterministic FSA that does the job then turn it into a FSA.
Another solution is to create a set of states representing the last one or two inputs, namely 0, 1, 00, 01, 10, 11 in addition to a start state. The transitions are obvious. 1 is emitted when transitioning from 01 to 11 or from 10 to 00. In fact state 11 can be merged with state 1 and state 00 can be merged with state 0. That leaves us with a total of 5 states that should do the job. I assume here that the outputs are emitted upon transitioning. Assuming the output is emitted upon entering a state, then states made of the last 3 inputs need to be made. Similarly, some states can be merged.