2. Let G0be the context free word grammar in Greibach normal form with axiom X, non terminals X0, Y0, Z0terminals a, b, and rules l
X0→ aX0Y0 X0→ aY0 X0→ aX0Z0 X0→ aZ0 Y0→ bX0 Z0→ b
prove that L(G0) = L(G). Give a derivation tree for u = aabbab.
3. Find a context free word grammar G00such that L(G00) = A1∪ A2 (A1 and A2
are defined in Exercise 28). Give two derivation trees for u = abc.
Exercise 30. Let F be a ranked alphabet.
1. Let L and L0 be two regular tree languages. Compare the sets Yield (L ∩ L0) and Yield (L) ∩ Yield (L0).
2. Let A be a subset of F0. Prove that T (F , A) = T (F ∩ A) is a regular tree language. Let L be a regular tree language over F , compare the sets Yield (L ∩ T (F , A)) and Yield (L) ∩ Yield (T (F , A)).
3. Let R be a regular word language over F0. Let T (F , R) = {t ∈ T (F ) | Yield(t) ∈ R}. Prove that T (F , R) is a regular tree language. Let L be a regu-lar tree language over F , compare the sets Yield (L ∩ T (F , R)) and Yield (L) ∩ Yield(T (F , R)). As a consequence of the results obtained in the present exer-cise, what could be said about the intersection of a context free word language and of a regular tree language?
2.7 Bibliographic notes
This chapter only scratches the topic of tree grammars and related topics. A useful reference on algebraic aspects of regular tree language is [GS84] which contains a lot of classical results on these features. There is a huge litterature on tree grammars and related topics, which is also relevant for the chapter on tree transducers, see the references given in this chapter. Systems of equations can be generalized to formal tree series with similar results [BR82, Boz99, Boz01, Kui99, Kui01]. The notion of pushdown tree automaton has been introduced by Guessarian [Gue83] and generalized to formal tree series by Kuich [Kui01] The reader may consult [Eng82, ES78] for IO and OI grammars. The connection between recursive program scheme and formalisms for regular tree languages is also well-known, see [Cou86] for instance. We should mention that some open problems like equivalence of deterministic tree grammars are now solved using the result of Senizergues on the equivalence of deterministic pushdown word automata [S´en97].
Chapter 3
Logic, Automata and Relations
3.1 Introduction
As early as in the 50s, automata, and in particular tree automata, played an important role in the development of verification . Several well-known logicians, such as A. Church, J.R. B¨uchi, Elgott, MacNaughton, M. Rabin and others contributed to what is called “the trinity” by Trakhtenbrot: Logic, Automata and Verification (of Boolean circuits).
The idea is simple: given a formula φ with free variables x1, ..., xn and a do-main of interpretation D, φ defines the subset of Dn containing all assignments of the free variables x1, . . . , xn that satisfy φ. Hence formulas in this case are just a way of defining subsets of Dn (also called n-ary relations on D). In case n = 1 (and, as we will see, also for n > 1), finite automata provide another way of defining subsets of Dn. In 1960, Bchi realized that these two ways of defining relations over the free monoid {0, . . . , n}∗ coincide when the logic is the sequential calculus, also called weak second-order monadic logic with one successor, WS1S. This result was extended to tree automata: Doner, Thatcher and Wright showed that the definability in the weak second-order monadic logic with k successors, WSkS coincide with the recognizability by a finite tree au-tomaton. These results imply in particular the decidability of WSkS, following the decision results on tree automata (see chapter 1).
These ideas are the basis of several decision techniques for various logics some of which will be listed in Section 3.4. In order to illustrate this correspon-dence, consider Presburger’s arithmetic: the atomic formulas are equalities and inequalities s = t or s ≥ t where s, t are sums of variables and constants. For in-stance x+y+y = z+z+z+1+1, also written x+2y = 3z+2, is an atomic formula.
In other words, atomic formulas are linear Diophantine (in)equations. Then atomic formulas can be combined using any logical connectives among ∧, ∨, ¬ and quantifications ∀, ∃. For instance ∀x.(∀y.¬(x = 2y)) ⇒ (∃y.x = 2y + 1)) is a (true) formula of Presburger’s arithmetic. Formulas are interpreted in the natu-ral numbers (non-negative integers), each symbol having its expected meaning.
A solution of a formula φ(x) whose only free variable is x, is an assignment of x to a natural number n such that φ(n) holds true in the interpretation. For
0
Figure 3.1: The automaton with accepts the solutions of x = y + z
instance, if φ(x) is the formula ∃y.x = 2y, its solutions are the even numbers.
Writing integers in base 2, they can be viewed as elements of the free monoid {0, 1}∗, i.e. words of 0s and 1s. The representation of a natural number is not unique as 01 = 1, for instance. Tuples of natural numbers are displayed by stacking their representations in base 2 and aligning on the right, then complet-ing with some 0s on the left in order to get a rectangle of bits. For instance the pair (13,6) is represented as 10110110 (or 0010110110 as well). Hence, we can see the solutions of a formula as a subset of ({0, 1}n)∗ where n is the number of free variables of the formula.
It is not difficult to see that the set of solutions of any atomic formula is recognized by a finite word automaton working on the alphabet {0, 1}n. For instance, the solutions of x = y + z are recognized by the automaton of Figure 3.1.
Then, and that is probably one of the key ideas, each logical connective corresponds to a basic operation on automata (here word automata): ∨ is a union, ∧ and intersection, ¬ a complement, ∃x a projection (an operation which will be defined in Section 3.2.4). It follows that the set of solutions of any Presburger formula is recognized by a finite automaton.
In particular, a closed formula (without free variable), holds true in the interpretation if the initial state of the automaton is also final. It holds false otherwise. Therefore, this gives both a decision technique for Presburger formu-las by computing automata and an effective representation of the set of solutions for open formulas.
The example of Presburger’s arithmetic we just sketched is not isolated.
That is one of the purposes of this chapter to show how to relate finite tree automata and formulas.
In general, the problem with these techniques is to design an appropriate notion of automaton, which is able to recognize the solutions of atomic formulas and which has the desired closure and decision properties. We have to cite here the famous Rabin automata which work on infinite trees and which have indeed the closure and decidability properties, allowing to decide the full second-order monadic logic with k successors (a result due to M. Rabin, 1969). It is however out of the scope of this book to survey automata techniques in logic and com-puter science. We restrict our attention to finite automata on finite trees and refer to the excellent surveys [Rab77, Tho90] for more details on other applica-tions of automata to logic.