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.

Alenanno
  • 9,388
  • 5
  • 48
  • 80
user65526
  • 229
  • 1
  • 2
  • 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 08 '14 at 18:13
  • I will be surprised if anyone here can provide insightful guidance about those topics. – Tim Osborne Apr 08 '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 08 '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 09 '14 at 10:42
  • I definitely second @babou's reference for the 2nd edition (it's a lot better than later editions) of Hopcroft & Ullman's intro to formal language theory. That was my entry-point to this subject area. I happen to have a PDF copy of the Levelt textbook by the way - Send me an email if you're interested. You can find my email add. on my profile page. – P Elliott Apr 09 '14 at 12:33
  • @PElliott Thanks - Actually, many of his books, not all, seem to be available on his site. Which book did you have in mind? – babou Apr 09 '14 at 14:08
  • 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 09 '14 at 15:40
  • Cross-posted: https://cs.stackexchange.com/q/23557/755, https://linguistics.stackexchange.com/q/6928/10726. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. – D.W. Jul 05 '17 at 17:30
  • I would highly recommend the book "An Introduction to The Theory of Computation" by Sipser. – Poscat Oct 19 '23 at 00:58

0 Answers0