Good introductions to Formal Language Theory and Formal Grammars
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:
<PERSON>’s theorem
<PERSON>' proof that <PERSON>-calculus grammars define only context-free stringsets
-the theorem of <PERSON>, <PERSON> and <PERSON>
<PERSON>’s theorem and <PERSON>’s theorem
<PERSON> review http://www.lel.ed.ac.uk/~gpullum/Rev_Kracht.pdf has put me off reading a book called "The Mathematics of Language" by <PERSON>, 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 <PERSON> assumes a lot of mathematical sophistication: graduate students whose first degree is in humanities or social science may experience symbol shock. <PERSON> does not pamper those who crave intuitive presentations. 330
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:
"<PERSON> truly excellent 3-volume 1974 textbook [6] had remarkably wide coverage (<PERSON> psycholinguistic interests lead him to cover work on ‘learnability’, also known as grammar induction, which <PERSON> does not touch on), but sadly has long been out of print. And the standard text by <PERSON>, <PERSON> and <PERSON> [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 <PERSON>’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. 469