2
$\begingroup$

Does anyone know any good introductions to Formal Language theory and Formal Grammar, that cover 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 http://www.lel.ed.ac.uk/~gpullum/Rev_Kracht.pdf has put me off reading a book called "The Mathematics of Language" by Markus Kracht, since I am not sure I have the required level of mathematical maturity. 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 \colon~ \delta(\{i_0\},x)\cap F \neq \emptyset\}$."

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.

$\endgroup$

closed as off-topic by D.W. Jul 5 '17 at 17:31

  • This question does not appear to be about computer science within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ While there is nothing wrong in starting with an accessible text, be aware (in case you aren't already) that eventually, you will have to be comfortable with heavy formalism - the field's name is formal languages, after all. $\endgroup$ – collapsar Apr 8 '14 at 18:27
  • $\begingroup$ I am comfortable with formalism. I just want an introduction which eases the way into the field. You've got to start somewhere. $\endgroup$ – user65526 Apr 8 '14 at 18:55
  • $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – FrankW Apr 8 '14 at 23:11
  • 1
    $\begingroup$ I can't remember if it covers everything in your list (it is an older book), but "Introduction to Formal Language Theory" by Harrison is one of the best introductions I've seen. $\endgroup$ – Pseudonym Apr 8 '14 at 23:30
  • $\begingroup$ Cross-posted: cs.stackexchange.com/q/23557/755, 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. $\endgroup$ – D.W. Jul 5 '17 at 17:30