Re: context free languages under SCRAMBLE operation

TheGist wrote:
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.

How? Let L = (01)^*. What's the DFA that accepts L' = SCRAMBLE(L)?
(L' contains the words that have n zeros and n ones for some n, which
doesn't smell regular to me. Maybe I'm missing something.)

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.
Is that a sufficient proof?

No. Let L = (cab)^*. SCRAMBLE(L) != {a^n b^n c^n : n >= 0}.
.

Relevant Pages

  • Re: trying to use the pumping lemma
    ... Here is my proof using the pumping lemma. ... assume L is a regular language accepted by some DFA M of s states. ... is a string in L that is "long enough" (in your notation, ...
    (comp.theory)
  • Re: RegExp as Finite State Machine
    ... RegExp is a FSM, both describe a regular language. ... language it accepts is regular -- Regular Expressions. ...
    (comp.lang.javascript)
  • Re: REGEXPS
    ... if you want to parse ... it's not a regular language so you need a parser. ... Lisp is not dead, it just smells funny. ...
    (comp.lang.lisp)
  • Re: REGULAR-TM is undecidable?
    ... Rick Decker wrote: ... >> R can decide whether X accepts a regular language. ... If M doesn't accept w, then the only strings X_M,w accepts are ...
    (comp.theory)
  • Re: Pumping Lemma Palindrome
    ... 10} where w^r is w reverse is not a regular language using the pumping ... Is it safe to assume that since palindromes are not regular, ... prof obviously wants you to prove the fact using the pumping lemma. ...
    (comp.theory)