I have an assignment, which is solved by making an FDA out of the information given, then figuring out the CFG out of the FDA, but I’m having trouble doing that step. Any help is appreciated! Here is the picture of the exercise:
A token is dorpped from A, B or C. The two keys (-.- these things) make the token go right or left depending on the position in which they are in (the token falls parallel to the direction of the key). When a token passes through a key, it makes it switch positions so that the next token that passes through goes in the opposite direction than the last.
What I have to do is write a program in python that, given a string (eg ABCAAAC, meaning a token was dropped from A, then another from B, then another from C, etc.) I have to determine wether or not it belongs to the language composed of the strings in which the last character (the last tken dropped) falls from exit one. To do this, first I figured out the automaton that models this behaviour, and the next step would be figuring out the grammar for that language by looking/doing smth with the FDA (I have to do it this way, not with regex).
Here is the picture of the FDA, I’m not sure it’s correct: