Game Development Reference
2.5 Beyond finite automata
In the previous sections we have considered games with winning conditions
that can be described by finite automata. In this section we briefly discuss
what happens if we move to non-regular winning conditions. A widely used
extension of regular languages are the context-free languages, which can
be defined in terms of context-free grammars or pushdown automata (see
Hopcroft and Ullman , Sipser ). Even though we are interested
in specifications over infinite words, we can use context-free languages of
finite words, for example, we can declare a play winning for Eva if it does
not contain a prefix that belongs to a given context-free language. Let us
refer to this kind of winning condition as a context-free safety condition.
Proposition 2.21 The problem of finding the winner in a game ( G, Win ) ,
where Win is a context-free safety condition is undecidable.
Proof We can give a reduction to the universality problem for context-free
languages, i.e., the question of whether a given context-free language contains
all words. This problem is known to be undecidable (e.g., Theorem 5.10 of
Sipser  or Theorem 8.11 of Hopcroft and Ullman ).
Let L be a context-free language over some alphabet Σ. We aim at con-
structing a context-free safety game such that Eva has a winning strategy iff
L =Σ ∗ . The game graph consists only of vertices for Adam, one for each
symbol from Σ. The edge relation contains all possible edges. This means
that Adam can freely choose a sequence over Σ. If we now consider the
context-free safety condition defined by L , then one can easily see that Eva
has a winning strategy iff L =Σ ∗ . Otherwise Adam can simply play the
sequence corresponding to a word not in L .
At the beginning of Section 2.3 we have considered the same kind of
winning condition for regular languages. There we could easily solve the
games by constructing a DFA for the given language and then solving a
simple safety game on a finite graph. For context-free languages this does
not work for two reasons. First of all, context-free languages are accepted by
pushdown automata, and therefore taking the product with a finite graph
will result in an infinite graph. Furthermore, we have seen that the method
does not work if we use non-deterministic automata instead of DFAs (see
Exercise 2.1). For the class of context-free languages deterministic pushdown
automata are not enough, the non-determinism is required.
What happens if we avoid the second problem by considering winning
conditions specified by deterministic pushdown automata? In fact, we can
consider deterministic pushdown automata over infinite words by simply