Reading group: Formal Languages and complexity

Are you interested in the computational complexity of language? In this reading group we’ll discuss how well different classes of formal grammars (e.g. regular and context-free) capture natural language phenomena, from phonology to syntax, as well as what these formal models might tell us about the cognitive and neural bases of language.

Depending on people’s interests, we could read papers taking us in several interesting directions; e.g:

• How does the complexity of human language compare to nonhuman vocalizations?
• How does human music fit into the Chomsky Hierarchy?
• How well do domain boundaries in linguistics line up with complexity differences?

For our first meeting, if you have time, let’s read this paper, which is a good introduction to Formal Language Theory, and brings in some finer-grained distinctions as well:

Jäger, G., & Rogers, J. (2012). Formal language theory: refining the Chomsky hierarchy. Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences, 367(1598), 1956–70. https://doi.org/10.1098/rstb.2012.0077