4 ms·

Traces of recursion have been found in animal "language" also - https://www.nature.com/scitable/blog/cognoculture/the_less_human_humans_recursion/ https://www.n

• foldr 6y ago
  The studies on song birds have for the most part been very poorly conceived and based on a simple misunderstanding. (The fact that a grammar can be defined using recursive rules doesn't entail that its string language can't be recognized by non-recursive procedures.) For example, the common A^nB^n string language (which can be defined using a recursive CFG) can obviously also be recognized by counting.
  • YeGoblynQueenne 6y ago
    But the a^nb^n language is context free so there is no regular grammar that can represent it. If a couting mechanism can be used to represent a^nb^n the result will still have to be a context-free grammar, otherwise a^nb^n would not be context-free.
    • foldr 6y ago
      No, that's exactly the mistake. You can check that the counts are equal without parsing the string at all. So the ability to recognize the string language is not evidence that the string is being parsed according to a particular CFG (or any other grammar). In other words, it is not evidence that the birds are pairing up each A with the corresponding B. Most of the literature on birds stems from a confusion of the distinction between regular string languages and context free string languages with the distinction between grammars with and without recursive rules. The two distinctions are largely orthogonal. It is certainly possible, for example, to define certain regular string languages using recursive grammars, and to define certain context free string languages without using recursive grammars. When you say that "the result must be a context free grammar" I think what you mean to say is that the string language defined must be a context free (and non-regular) string language. But that does not in any way entail that the only way to recognize the string language is by means of a particular context free grammar.
      • deleted 6y ago
        [deleted]
      • YeGoblynQueenne 6y ago
        Ah, I see - my mistake. You're saying that one can count n "a"s followed by n "b"s without the need for a context-free grammar (or any grammar!). I agree. What I meant by "the result will still have to be a context free grammar" was a context-free grammar that incorporates a counting mechanism, as part of its definition. Something like this, perhaps (in Definite Clause Grammars notation so you can actually run it as a Prolog program): 'S' --> 'A'(N), 'B'(N). 'A'([1]) --> 'A'. 'A'([1|As]) --> 'A', 'A'(As). 'B'([1]) --> 'B'. 'B'([1|Bs]) --> 'B', 'B'(Bs). 'A' --> [a]. 'B' --> [b]. Though that one is recursive (or at least the counting mechanism is) and I'm not sure how you'd do the same thing without recursion to be honest (or without going up a couple of levels to Turing-completeness so you can call arbitrary functions). So, never mind- I just misunderstood what you meant.
        • foldr 6y ago
          I see, fair enough. I think I may have misread your original comment.
          • YeGoblynQueenne 6y ago
            No, I misread yours :)