How can we describe the complexity of linguistic systems? Where does natural language fit in? In this week's episode, we talk about the Chomsky hierarchy: what it captures, what characterizes different kinds of grammars on the hierarchy, and whether we can find grammars that sit higher on the scale than human language.

This is Topic #63!

This week's tag language: Croatian!

Related topics:
Happy Little Trees: X' Theory -    • Syntactic Trees and X' Theory  
Trace Evidence: Syntactic Movement -    • Syntactic Movement and Traces  

Last episode:
Quantifying Sets and Toasters: Generalized Quantifiers -    • What Does "Most" Even Mean? Generaliz...  

Other of our syntax and morphology videos:
Raising the Bar: Raising and Control Verbs -    • What Changes in a Sentence When We Sw...  
Organizing Meanings: Morphological Typology -    • Systems of Morphemes  
Referential Treatment: Binding Theory -    • Binding Theory and Interpreting Pronouns  

Also, if you'd like to know more about the Chomsky Hierarchy and its impact on computer science, Computerphile's had a few videos about them:
- Their episode on the hierarchy:    • Chomsky Hierarchy - Computerphile  .
- Their episode about finite-state machines:    • Computers Without Memory - Computerphile  .
- And their episode about how finite-state machines relate to grammar:    • Same Story, Different Notation - Comp...  .


Find us on all the social media worlds:
Tumblr:   / thelingspace  
Twitter:   / thelingspace  
Facebook:   / thelingspace  

And at our website, http://www.thelingspace.com/ !
You can also find our store at the website, https://thelingspace.storenvy.com/

Our website also has extra content about this week's topic at http://www.thelingspace.com/episode-63/

We also have forums to discuss this episode, and linguistics more generally.

Sources:
(1) I-Language (1st Edition, Daniela isac & Charles Reiss)
(2) Introduction to the Theory of Computation (3rd Edition, Michael Sipser)
(3) Mathematical Logic for Computer Science (3rd Edition, Mordechai Ben-Ari)
(4) Evidence Against the Context-Freeness of Natural Language (Stuart Shieber - http://www.eecs.harvard.edu/~shieber/...)
(5) https://en.wikipedia.org/wiki/Chomsky...
(6) Syntactic Structures (Noam Chomsky)
(7) Mathematical Methods in Linguistics (Barbara Partee, Alice G. ter Meulen, Robert Wall)

Proof regarding crossing dependencies (adapted from the first edition of Introduction to Automata Theory, Languages, and Computation, by John Hopcroft and Jeffrey Ullman. Note where carets appear that the following character should be taken as superscript):

We first capture the general pattern of embedded clauses in Swiss German with the language a^nb^mc^nd^m . We then treat this as the result of intersecting Swiss German with the regular language a*b*c*d*.

Now, let L = {a^nb^mc^nd^m | n ≥ 1 and m ≥ 1}. Suppose L is a context-free language, and let p be the pumping length referred to in the pumping lemma for context-free languages (https://en.wikipedia.org/wiki/Pumping.... Consider the string z = a^pb^pc^pd^p. Let z = uvwxy satisfy the conditions of the pumping lemma. Then as |vwx| ≤ p, vx can contain at most two different symbols. Furthermore, if vx contains two different symbols, they must be consecutive, for example, a and b. If vx has only a’s, then uwy has fewer a’s than c’s and is not in L, a contradiction. We proceed similarly if vx consists of only b’s, only c’s, or only d’s. Now suppose that vx has a’s and b’s. Then uwy still has fewer a’s than c’s. A similar contradiction occurs if vx consist of b’s and c’s or c’s and d’s. Since these are the only possibilities, we conclude that L is not context-free.

Since context-free languages are closed under intersection with regular languages, and the above intersection is not context-free, Swiss German must be non-context-free.

Q.E.D.

A proof of the pumping lemma itself can be found in Introduction to the Theory of Computation (among other places). For a discussion of the closure properties of context-free languages, see Mathematical Methods in Linguistics (among other places).

Looking forward to next week!