This is Automata and Formal Languages. I don't know how to solve these problem.
Notice that a PDA could have a move that does not read from the input (only performs stack operation and state transition). Therefore, it is possible for the PDA to run forever on some given input. Prove that there is an algorithm that answers whether, for a given PDA, there is an input word on which the PDA has an infinite execution. Let be a finite set of colors, and G be a directed graph on which each arc is labeled with a color in E. An w-walk is an infinite path VOCOVICV2. on G such that, for each i, G has an arc from v; to Vi+1 with color ci. In particular, we say the walk starts from vo. The walk is fair if there are infinitely many prefixes of the walk on which the number of red arcs, the number of green arcs and the number of blue arcs are all the same. Prove that there is an algorithm to decide whether the graph G has a fair walk starting from a given node vo. In finite automata, there is no concept about time; or we can think in this way: each move takes one unit time. But in reality (e.g., in designing an embedded system), timing is an explicit requirement which can be expressed through timers. Timers can be used to control moves of the automata. Investigate your ways of adding timers to the definition of finite automata (hence your extended finite automata are able to describe a simple class of real-time systems). Notice that a PDA could have a move that does not read from the input (only performs stack operation and state transition). Therefore, it is possible for the PDA to run forever on some given input. Prove that there is an algorithm that answers whether, for a given PDA, there is an input word on which the PDA has an infinite execution. Let be a finite set of colors, and G be a directed graph on which each arc is labeled with a color in E. An w-walk is an infinite path VOCOVICV2. on G such that, for each i, G has an arc from v; to Vi+1 with color ci. In particular, we say the walk starts from vo. The walk is fair if there are infinitely many prefixes of the walk on which the number of red arcs, the number of green arcs and the number of blue arcs are all the same. Prove that there is an algorithm to decide whether the graph G has a fair walk starting from a given node vo. In finite automata, there is no concept about time; or we can think in this way: each move takes one unit time. But in reality (e.g., in designing an embedded system), timing is an explicit requirement which can be expressed through timers. Timers can be used to control moves of the automata. Investigate your ways of adding timers to the definition of finite automata (hence your extended finite automata are able to describe a simple class of real-time systems)
