For strings w and t. write w = t if the symbols of w arc a permutation of the sy
ID: 3639351 • Letter: F
Question
For strings w and t. write w = t if the symbols of w arc a permutation of the symbols of t. In other words, w = t if t and w have the same symbols in the same quantities, but possibly in a different order. For any string w, define SCRAMBLE(w) {t | t = w). For any language let SCRAMBLE(A) = { t | t SCRAMBLE(w) for some w A). Show that, if {0,1}, then the SCRAMBLE of a regular language n context free. What happens in part (a) if contains 3 or more symbols? Prove your answer.Explanation / Answer
For part (a) I think this can be proven by simply noting that the DFA which accepts the regular language to be scrambled can simply have its state transitions re-arranged to accept the SCRAMBLE of the language. This is de facto context free since every regular language is in turn context free. Am I right? For part (b) if the language of (a) has 3 or more symbols than it is not context free, I believe, however I am not sure how to prove this? Perhaps a counter example? How about this counter example, The language containing strings like cabcab is obviously regular, however we know from a previous result that strings of the form a^nb^nc^n n>=0 are not context free.