5

The Chomsky hierarchy of types 0,1,2,3 grammars correspond, as he showed, to the abstract automata classified in accordance with their use of memory. The type 2 grammars, the context free phrase structure grammars, are computationally equivalent to the push-down store automata (which Chomsky was the first to characterize), which use memory as a push-down stack. Stacks are the mechanism by which computer programs call subroutines. The push-down stack is accessed by push and pop instructions, which store and retrieve memories on the stack.

The fact that a push-down stack is in use explains why both human languages and modern high-level programming languages have hierarchical tree structures, since the items below a node in a tree structure correspond to a subroutine in programming.

Yet, so far as I know, nothing neurological corresponding to memory pushes and pops has been discovered by brain scientists. This is a puzzle. Can anyone help?

Improve this question
22
  • 1
    Entering subroutines (and, importantly, then continuing execution of the outer routine) happens in tasks outside language, and other animals do it too, right? For example, creating or just finding a tool for a task.
    – Adam Bittlingmayer
    Feb 27, 2020 at 17:23
  • @AdamBittlingmayer How is finding a tool for a task like a subroutine? Are the skills involved generalized to other tasks for, say, monkeys? Or octopuses?
    – Greg Lee
    Feb 27, 2020 at 17:40
  • 3
    My suggestion is that "computational equivalence" does not tell you what actual cognitive status is. But furthermore, brain scientists have yet to discover anything probative about the physical nature of language computation.
    – user6726
    Feb 27, 2020 at 17:57
  • I did some searching around, and there does appear to have been papers suggesting that your push/pop metaphor may be applicable to sentence processing, as well as arguments against..
    – WavesWashSands
    Feb 28, 2020 at 6:33
  • 1
    And this paper finds evidence for statistical learning of chunkns in Bengalese finches, so they appear to use the same mechanisms that humans use to learn constituents/chunks as well.
    – WavesWashSands
    Feb 28, 2020 at 6:53

1 Answer 1

Reset to default
2

I'm sure you know more about this than I do, but problems like center embedding make me question whether push/pop memory is a useful abstraction for human brain. Quoting Wikipedia:

A man that a woman that a child that a bird that I heard saw knows loves.

If human brains actually possessed unlimited (or even reasonably limited) push/pop memory, we would have no problem parsing this. The fact that we don't suggests, to me, that a human brain's capacity for "push/pop" operation is really limited.

Also, one must be careful when reasoning about mathematical models. Push-down automata (PDA) are mathematically equivalent to CFG, loosely speaking, but it is not the only computational model that can recognize CFG. For example, CYK algorithm can also parse all context-free languages, but its structure looks very different from a stack!

Improve this answer
6
  • I agree that whether CFG is too powerful for modelling natural language is open to serious doubt. Keeping this in mind, don't you have some reservations about recommending a still more powerful model?
    – Greg Lee
    Mar 3, 2020 at 1:35
  • Sorry, I'm not exactly sure what you mean - I'm not a linguist and only have a passing familiarity with theory of computer languages. Anyway, my personal opinion (as layperson) is to heed: "All models are wrong, but some are useful." A computational model can be still useful if it reflects some part of human languages well, even if it fails for the rest.
    – jick
    Mar 3, 2020 at 3:37
  • The class of pda, push-down store automata, is not a parsing algorithm, so I don't know how to compare it to the CYK algorithm. Do you mean that a computer executing the CYK algorithm does not use a push-down stack? I find that hard to believe.
    – Greg Lee
    Mar 3, 2020 at 18:00
  • As far as I understand, the set of languages that can be parsed by (vanilla) CYK algorithm is exactly the set of context-free languages. As you can see from the wiki page, the algorithm doesn't really use a stack. Of course, any modern computer executing the algorithm would use an execution stack, but then again such a computer will most likely also have a silicon-based random-access memory, and we don't consider "silicon-based RAM" an integral part of CYK algorithm.
    – jick
    Mar 3, 2020 at 18:33
  • Pda is not an algorithm! It's not a program or a class of programs. It's a class of machines using the pd memory discipline (which is not random access memory).
    – Greg Lee
    Mar 3, 2020 at 18:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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