4. A robot is walking on a 2D-grid. It receives instructions from the set = {N,...

Transcribed Image Text:

4. A robot is walking on a 2D-grid. It receives instructions from the set = {N, W, S, E}, which indicate a move 1 step to the north, west, south and east, respectively. The robot starts at the origin, and receives an instruction string *. The robot wants to know whether it is at the origin after executing x. Prove that if the robot uses a DFA, it cannot answer this question. 4. A robot is walking on a 2D-grid. It receives instructions from the set = {N, W, S, E}, which indicate a move 1 step to the north, west, south and east, respectively. The robot starts at the origin, and receives an instruction string *. The robot wants to know whether it is at the origin after executing x. Prove that if the robot uses a DFA, it cannot answer this question.