f



Help needed with problem

Can someone help me out with this problem. Any help is appreciated.
Thanks.

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').
0
stegen123 (14)
9/23/2003 5:29:21 AM
comp.theory 5139 articles. 1 followers. marty.musatov (1143) is leader. Post Follow

2 Replies
487 Views

Similar Articles

[PageSpeed] 46

Jack you're an idiot.  See my other post.  Get off of usenet and find a
job at a bar where your mental capacities are on par with the subjects you
converse with.


-c


On Mon, 22 Sep 2003 22:29:21 -0700, Jack Smith wrote:

> Can someone help me out with this problem. Any help is appreciated.
> Thanks.
> 
> 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').

0
blunck1 (18)
9/25/2003 3:16:34 AM
Christoper: Why flame the noob?  There's no reason for it.  Does he
intimidate you?  Did you graduate at the bottom of your class and feel
your helpdesk job might be in jeopardy?

Jack: It's been a while since I saw this kind of material.  I'm not
sure how your prof wants this problem explained (most likely by
mathematical proof), so let me suggest that you use proof by
contradiction.  That usually is an acceptable way to prove
computational theory questions, especially when talking about regular
expressions over languages.


"Christopher Blunck" <blunck@gst.com> wrote in message news:<pan.2003.09.25.03.16.32.764257@gst.com>...
> Jack you're an idiot.  See my other post.  Get off of usenet and find a
> job at a bar where your mental capacities are on par with the subjects you
> converse with.
> 
> 
> -c
> 
> 
> On Mon, 22 Sep 2003 22:29:21 -0700, Jack Smith wrote:
> 
> > Can someone help me out with this problem. Any help is appreciated.
> > Thanks.
> > 
> > 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').
0
schigh (33)
9/28/2003 9:14:30 PM
Reply: