Regular Languages. Help Needed.

[Jack Smith]

I posted this question earlier, but I got no responses. Can anyone
help me out here...any hints or even how to start? Thanks in advance.

Let doubleswap(x) be the string formed by replacing each a in x by the
substring bb and each b by the substring aa. For example,
doubleswap(abcab)=bbaacbbaa. Furthermore, let doubleswap(L) be the
language formed of strings doubleswap(x) for x an element of L. Prove
that if L is regular, then so is doubleswap(L). Where L is a subset
(or equal) to {a, b, c}^*.

If L is regular, the L can be expressed as L(y) for some regular
expression y. We define y' to be the same as y except that we replace
each a in y by a pair of b's and each b by a pair of a's. Since y' is
a regular expression, it will suffice to show that L(y') =
doubleswap(L).

(a) Prove that L(y') is a subset or equal to doubleswap(L).

(b) Prove that doubleswap(L) is a subset or equal to L(y').

[Brad BARCLAY]

Jack Smith wrote:

I posted this question earlier, but I got no responses. Can anyone
help me out here...any hints or even how to start? Thanks in advance.

Actually, looking here you had _several_ responses.

However, the question you're asking is _not_ a Java question, so you're
asking it in the wrong newsgroup. The question is off-topic. Please ask
your question in the relevant math newsgroup instead.

Brad BARCLAY

--
=-=-=-=-=-=-=-=-=
From the OS/2 WARP v4.5 Desktop of Brad BARCLAY.
The jSyncManager Project: http://www.jsyncmanager.org


[Shyamal Prasad]

"stegen123" == stegen123 <st*******@yahoo.com> writes:

stegen123> I posted this question earlier, but I got no responses.
stegen123> Can anyone help me out here...any hints or even how to
stegen123> start? Thanks in advance.

Asking homework questions on usenet is generally frowned upon ;-)

stegen123> Let doubleswap(x) be the string formed by replacing
stegen123> each a in x by the substring bb and each b by the
stegen123> substring aa. For example, doubleswap(abcab)=bbaacbbaa.
stegen123> Furthermore, let doubleswap(L) be the language formed
stegen123> of strings doubleswap(x) for x an element of L. Prove
stegen123> that if L is regular, then so is doubleswap(L). Where
stegen123> L is a subset (or equal) to {a, b, c}^*.

You are asking for a hint???? That is what you have below!

stegen123> If L is regular, the L can be expressed as L(y) for
stegen123> some regular expression y. We define y' to be the same
stegen123> as y except that we replace each a in y by a pair of
stegen123> b's and each b by a pair of a's. Since y' is a regular
stegen123> expression, it will suffice to show that L(y') =
stegen123> doubleswap(L).

stegen123> (a) Prove that L(y') is a subset or equal to
stegen123> doubleswap(L).

stegen123> (b) Prove that doubleswap(L) is a subset or equal to
stegen123> L(y').

It is a well known result that regular sets are closed under
complementation, intersection, and substitution. Look up a good text
on automata theory.

You generally show subset properties by picking an element in the
first set and showing why it must be in the other one.

Or try and express this as a problem for a Java regex package. You
might get more responses :-)

Cheers!