6

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.

8
  • 1
    Edward, welcome to Linguistics SE. Allow me to give you a suggestion. Asking for "recommendation" is not really OK on the SE sites because it's mostly about opinions. However, since you posted 4 points you wanted to know more about, I'd suggest you ask them as separate questions. That way users can focus on each answer separately and more in depth. You'll also be able to gain more reputation having four different questions (if reasonably unrelated). – Alenanno Apr 8 '14 at 18:13
  • I will be surprised if anyone here can provide insightful guidance about those topics. – Tim Osborne Apr 8 '14 at 18:21
  • 1
    I wonder if you have noticed that "The Mathematics of Language" is available as a free PDF from the author's university website. So you might want to check for yourself if the shortcomings that Pullum mentioned are applicable to you, given your own background, and Kracht's explanations. – prash Apr 8 '14 at 23:22
  • I just looked at "The Mathematics of Language". I am not scared by formalism, but it can be very dry reading. I would suggest any known introductory book on automata theory and computability with a general background. Choosing a reference book just for 2 or 3 theorems may not be a great idea. Specific theorems as you mention can always be added later by looking into appropriate references or other books. My own base book is the old Hopcroft+Ullman-1979, but I am sure there are many others. It may be dated, with missing results. They all are, including Kracht's book which came 24 years later. – babou Apr 9 '14 at 10:42
  • 1
    @babou right you are! It's on his website. I had in mind the '74 book - My comment was primarily in response to this quote from Pullum's review: "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". So clearly the Levelt book is widely available again, if it wasn't before. – P Elliott Apr 9 '14 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.