Comments on Leniel Macaferi's blog: Regex engine in C# - the Regex Parser

Hey dev, Thanks for replying to this thread! I d...

2009-09-12T12:48:37.014-03:00

Hey dev,

Thanks for replying to this thread!

I didn't understand your point at first.

I read your second interaction carefully so that I could understand it.

You're right. The regex I've written doesn't describe the machine represented in figure 1.

I'll update the post with the regex you suggested. It's the right one.

Once again, thank you very much for pointing this out. That's the kind of thing that makes the internet so fascinating: the interchange of knowledge.

All the best,

Leniel Macaferi

I don't know follow up post got submitted or not, ...

2009-09-10T12:54:22.355-03:00

I don't know follow up post got submitted or not, so here is a brief repost.

What I originally meant to imply was:

fig 1 will reject "aab"
(a|b)(a|b)*(a|b) will accept "aab"

fig 1 enforces that the first and last char are the same, where as the regex only checks that it is an a or b.
Therefore, the that regex does not describe the language of figure 1.

Hi dev, If you look at Figure 1, you'll see that ...

2009-09-02T16:33:56.294-03:00

Hi dev,

If you look at Figure 1, you'll see that you have state 3 (s3) to be reached before you get the final state (s7).

If you input "aab", you'll have this sequence of states:

s0(ε) -- s1(a) -- s2(a) -- s2(b) -- s2

So as you can see, you get stuck at s2 and don't reach s3 that would led you to s7. This way the machine won't accept the input "aab" because you didn't reach the final state s7.

Hope this helps,

Leniel Macaferi

"What is the regular expression that describes the...

2009-09-02T12:44:06.082-03:00

"What is the regular expression that describes the machine M shown in Figure 1 above?
The language of M can be described by the regular language given by this regular expression: (a|b)(a|b)*(a|b)"

Would figure 1 not reject, and the regex accept "aab".
Should the instead regex be (a(a|b)*a)|(b(a|b)*b)
Please correct me if I am wrong. Thanks,