Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP

Loading…

Triple #8

Closed
camitz opened this Issue · 4 comments

2 participants

Martin Camitz Alok Menghrajani
Martin Camitz

Hello!

On your Triple solution you write:

At this point, we have something like X = a* | Xb | Xc, which can be expressed as X = (a | b | c)*:

Although a beginner at this sort of reasoning, I find myself not agreeing with you. The second matches aba for instance, but the first doesn't.

But then I find, well if so, how would I draw that state graph? Obviously my logic is off. Would you care to help me out?

Alok Menghrajani

You are totally right, something is wrong and thank you for taking the time to point it out!
X = a | Xb | Xc can only be expressed as X = a ( b | c )*

a is actually de, and b,c have de in their suffix, so we end up with something like:
de ( bde | cde )*

We can then convert anything that's x* ( y x* )* to ( x | y )*.
Do you agree and do you have a simple way to explain this?

If we continue, we end up with:
d* (e | bd* | cd)

e is equivalent to ed* (because e ends with d):
d
(ed* | bd* | cd)

Using the same x* ( y x* )* to ( x | y )* conversion we get:
(d | e | b | c)*

I'll fix the page and explain that:
x* is the same as xx
x* ( y x* )* is the same as (x | y)*

Martin Camitz

I agree with your statement, but I had to try it out on regexpal.com to be certain, by trying out random tappings of my keyboard. That's the only way I have to explain it: "If you don't believe me try it out on regexpal.com." That should flunk you from most college level classes. :)

Alok Menghrajani

:)

You can give http://regexp.quaxio.com/ a shot too. I lint (to some degree) and do some nice hovering stuff.

Alok Menghrajani

pieter pointed out that you can validate this using http://unnecessarytools.com/dprle/ and entering:

# x(?:yx)*
a < [ s: q0 # start state
f: q1 # final state
d: q0 -> q0 on {'x'}
q0 -> q1 on epsilon
q1 -> q2 on {'y'}
q2 -> q2 on {'x'}
q2 -> q1 on epsilon
];

# (?:x|y)*
b < [ s: q0
f: q0
d: q0 -> q0 on {'x', 'y'} ];

solve();
a ?= b;

Pretty cool. Doesn't seem to provide a proof though...

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.