9 events
when toggle format what by license comment
May 13 '11 at 19:58 comment added Raphael Yuval, I intended to build the complement of $\{ w_1\dots w_n \in \Sigma^* \mid i \neq j \leadsto w_i \neq w_j\}$, that is I considered the set of all permutations to include all permutations of subsets of the alphabet.
May 13 '11 at 17:57 comment added Yuval Filmus @Raphael: The complement should also include all "subpermutations". In particular, we could intersect it with the regular language $(A \setminus a)^{|A|-1}$ to get all permutations on $A \setminus a$, along with some "extras".
May 13 '11 at 13:27 comment added Raphael The complement is easily expressed as e.g. $S \rightarrow AaAaA, A \rightarrow aA | \epsilon$ for all $a \in \Sigma$.
May 13 '11 at 5:31 history tweeted twitter.com/#!/StackCSTheory/status/68911233734148096
May 13 '11 at 5:06 answer Yuval Filmus timeline score: 7
May 12 '11 at 23:23 comment added Tegiri Nenashi Let scope it to finite set of symbols and require a grammar of the size proportional (or growing moderately) with the number of terminals.
May 12 '11 at 23:03 comment added Mohammad Alaggan For any finite language, if you just iterate over all the member you could express it as a regular language. The problem is with infinite languages, and this is where we need patterns and higher level in the Chomsky hierarchy. Is your question is how to express permutations of an infinite set of symbols in a context free grammar ?
May 12 '11 at 22:44 history edited Tegiri Nenashi CC BY-SA 3.0
deleted 8 characters in body
May 12 '11 at 22:38 history asked Tegiri Nenashi CC BY-SA 3.0