Does anyone know any good introductions to Formal Language theory and Formal Grammar, that covers the mathematical basis of Syntax and things like context free grammars and pushdown automata? In particular, I'd like to be able to understand:
- Parikh’s theorem
- Pentus' proof that Lambek-calculus grammars define only context-free stringsets
- the theorem of Chandra, Kozen and Stockmeyer
- Bûchi’s theorem and Doner’s theorem
Geoffrey Pullum's review has put me of reading a book called "The Mathematics of Language" by Markus Kracht. He writes:
"Readers of The Mathematical Intelligencer will probably get on with it well enough, but others should be warned that Kracht assumes a lot of mathematical sophistication: graduate students whose first degree is in humanities or social science may experience symbol shock. Kracht does not pamper those who crave intuitive presentations. He will not explain that a finite automaton accepts exactly those strings on which there is a run beginning in the start state and ending in a final state; he will expect you to see that immediately when he tells you (on p.96) that L(A) = {⃗x : δ({i0},⃗x)∩F ̸= 0/}."
The review has also put me off several other introductions:
"W. J. M. Levelt’s truly excellent 3-volume 1974 textbook [6] had remarkably wide coverage (Lev- elt’s psycholinguistic interests lead him to cover work on ‘learnability’, also known as grammar induction, which Kracht does not touch on), but sadly has long been out of print. And the standard text by Partee, ter Meulen and Wall [9] is now more than fifteen years behind the leading edge of research, especially with respect to grammars and automata. (Though it was published in 1990, the Partee el al. volume reports as open the question of whether the complement of a context-sensitive stringset is always context-sensitive, which was settled in the affirmative in 1987, at Partee’s insti- tution!) Though strong on formal semantics, it completely misses important topics in other areas (parsing and computational complexity, for example), and it looks positively fusty beside Kracht’s much more up-to-date and considerably more mathematical book."
So I'd be grateful to hear if there are any introductions to this field which people can recommend.
