News for hackers. Stuff that matters.
Re:Talking is throwing fictional worlds at one another by YeGoblynQueenne on Tuesday September 15, 2020 @08:50AM (#24480613)
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.
Re:Talking is throwing fictional worlds at one another by foldr on Tuesday September 15, 2020 @08:58AM (#24480676)
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.

Re:Talking is throwing fictional worlds at one another by YeGoblynQueenne on Tuesday September 15, 2020 @10:57AM (#24481899)
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.
Re:Talking is throwing fictional worlds at one another by foldr on Tuesday September 15, 2020 @11:10AM (#24482049)
I see, fair enough. I think I may have misread your original comment.
Re:Talking is throwing fictional worlds at one another by YeGoblynQueenne on Tuesday September 15, 2020 @11:15AM (#24482108)
No, I misread yours :)