[10:23:47] i have a question! [10:23:52] the GF Tutorial says: Exercise. Define the language a^n b^n c^n in GF, i.e. any number of a's followed by the same number of b's and the same number of c's. This language is not context-free, but can be defined in GF by using discontinuous constituents. [10:24:20] i was learning more about that -- i remember (maybe in the book) reading that the a^n b^n c^n problem is the classic example of "you can't do that with a CFG" [10:24:50] and the tutorial says: [10:24:50] three deviations from context-free grammar: [10:24:50] permutation: changing the order of constituents [10:24:50] suppression: omitting constituents [10:24:52] reduplication: repeating constituents [10:25:00] [10:25:14] but then, i went off to look at https://www3.cs.stonybrook.edu/~warren/xsbbook/node31.html which deals with exactly the a^n b^n c^n challenge [10:28:03] i suppose allowing multiple symbols on the LHS is basically the same thing as allowing arguments in a compound term [10:35:42] is that right? and is that why warren calls it a CSG? [11:09:09] *** Joins: michmech (~Thunderbi@cst-prg-32-231.cust.vodafone.cz) [11:41:32] *** Quits: michmech (~Thunderbi@cst-prg-32-231.cust.vodafone.cz) (Ping timeout: 256 seconds) [13:07:00] *** Joins: michmech (~Thunderbi@cst-prg-32-231.cust.vodafone.cz) [13:24:05] *** Quits: michmech (~Thunderbi@cst-prg-32-231.cust.vodafone.cz) (Quit: michmech) [13:26:01] *** Joins: michmech (~Thunderbi@cst-prg-32-231.cust.vodafone.cz) [13:26:26] *** Quits: michmech (~Thunderbi@cst-prg-32-231.cust.vodafone.cz) (Client Quit) [14:13:56] never mind, i need to read more about the different categories of grammars [14:14:56] i think my understanding of the terminology is complicated by the fact that some of these papers were written a long time ago, and the taxonomy of CFG, CSG, PMCFG, PSG, etc etc has been evolving steadily [14:37:00] freeside: it is basically the turing hierarchy: regular < context-free < context sensitive < unrestricted grammars [14:37:46] but then you have grammars like pmcfg, hpsg, ..., which are difficult to fit into this hierarchy [14:38:10] so, you have two levels, the expressivity/complexity and the formalism itself [14:39:06] as far as i know pmcfg is considered mildly context-sensitive. proof: it can express a^n b^n c^n [14:41:56] another level to this is what kind of automaton you can use to recognize the language: regular languages equivalent to finite deterministic automata, context-free to pushdown automata, context-sensitive to linear-bound automata and so on [19:04:36] *** Quits: drbean (~drbean@TC210-63-209-78.static.apol.com.tw) (Ping timeout: 256 seconds) [19:08:43] *** Joins: drbean (~drbean@TC210-63-209-38.static.apol.com.tw) [22:51:21] *** Joins: michmech (~Thunderbi@cst-prg-32-231.cust.vodafone.cz) [23:07:36] *** Quits: michmech (~Thunderbi@cst-prg-32-231.cust.vodafone.cz) (Quit: michmech)