I know formal languages are widely used in linguistics, especially for computational linguistics. However, I do not understand where this connection started - Wikipedia says that formal language theory sprung out of linguistics but I would like to find a good introduction that will help me see the connection once and for all.

  • 1
    I'm not sure the term "formal language" was spoken once in my whole linguistics degree. If it was, it certainly played no significant role. And that was at a uni that taught Chomskian syntax. – curiousdannii Nov 8 '19 at 1:41
  • It wasn't in my whole undergrad degree either, but now that I am in grad school it seems to be all that my department talks about. To be fair though, the focus is computational linguistics. It's very interesting but even after a couple of years of grad school i still feel like i am just beginning to scratch the surface of it. – alpablo20 Nov 9 '19 at 20:31
  • 1
    Despite the history, contemporary Chomskian theory does not employ the assumptions of formal language theory. Instead, formal language theory is an area more relevant to GPSG / Categorial Grammar and descendants. FLT makes no sense w.r.t. the computational devices of Minimalism. – user6726 Nov 12 '19 at 18:41

I do not think there is a good "introduction", because you're referring to an era that preceding the modern trend of writing introductions.

The more-accessible "start" is Chomsky 1956 "Three models for the description of language" as well as 1959 "On certain formal properties of grammars". These works were not generally intelligible within linguistics, but the Chomsky hierarchy helped to define a fundamental research question – what kind of apparatus is required to formally describe human language? The hierarchy in particular caused linguists to focus on the concept of "power" / generative capacity. We knew that a system using only context-free rules is inherently superior to one using context-sensitive rules, and one using context-sensitive rules is superior to using unrestricted rewrite rules. Specifically, you can "do fewer things" with context-sensitive rules than you can with unrestricted rewrite rules, so unless unrestricted rewrite rules can be proven to be necessary, you should not embrace a theory with unrestricted rewrite rules, you should embrace a theory with context-sensitive rules. This consideration sort of fell by the wayside after about 15 years of generative grammar, when transformational rules fell out of fashion, but even to this day people talk about some theory being "too powerful", invoking the concepts of the Chomsky hierarchy (generally without any of the math).

The linguistic contributions to formal language theory seem to be fairly minimal.

  • "Inherently superior"? Simpler, perhaps, but that's a value judgement, not a fact. The esthetic of MITish grammar is the minimalist esthetic of mathematics -- the most elegant proof with the simplest assumptions wins -- but with arbitrary assumptions and no proofs. – jlawler Nov 7 '19 at 23:15

My first introduction was Bob Wall's introductory book, and, though it is dated, I still recommend it. It is based on the Chomsky hierarchy of formal languages.


The focus skews toward phonology, but Jeff Heinz's notes on this are quite good IMO:


Also, with slightly less focus on formal language theory (but still some), but a lot of motivation for computational linguistics, are Ed Stabler's (now quite old, but still great, and VOLUMINOUS) notes:


  • 1
    Yeah, I'm familiar w Jeff's stuff (currently studying in the same dept lol). I was just hoping I'd find something more syntax oriented. Thanks tho! I will give those notes a look again! – alpablo20 Nov 13 '19 at 23:56

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.