Game Development Reference

In-Depth Information

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 [1979], Sipser [1997]). 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 [1997] or Theorem 8.11 of Hopcroft and Ullman [1979]).

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

Search Nedrilad ::

Custom Search