2 ms·
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
by 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 agoI see, fair enough. I think I may have misread your original comment.
- YeGoblynQueenne 6y agoNo, I misread yours :)