7

I have been given an assignment to simulate an NFA in Java. Now the following regular expression that I have to simulate an NFA for is 

ab*((b|d)|c*)

I think I have too many e-symbols. I was just wondering if the following image below is correct.

NFA

Bill the Lizard
  • 398,270
  • 210
  • 566
  • 880
unleashed
  • 915
  • 2
  • 16
  • 35
  • Nodes 10, 11, 12 and 13 could probably be condensed into just two nodes? – Brandon Buck Nov 29 '11 at 22:37
  • That's what I though initially but the lecturer wants it that style using above for repeat and using Thompson construction to create the NFA. I'm just rather doubtful of 2 to 3 e transition, 3 to 4 e transition and 4 to 5 or 4 to 7 e transition. – unleashed Nov 29 '11 at 22:42
  • Well, the 2-3 could be reduced, in cases of `b*` resulting in no `b`s you'd have a `e` transition from 1-2. Other than that I think the rest of it seems appropriate. Ultimately the end result is the same, just one less node. – Brandon Buck Nov 29 '11 at 22:50
  • Although from looking at examples such as this http://t2.gstatic.com/images?q=tbn:ANd9GcRaijg4c8db5s7sQkjlmL_rRCynJE5vx_ZyWFInHPIKELeoq216sA it seems that there is an `e` transition from `2-3` in my case. I know it can be reduced but is that a correct way of doing it? From the (Compiler - principles, tools & techniques 2nd edition) book it shows examples similar to the link provided. – unleashed Nov 29 '11 at 22:59
  • If that is a correct example I would say you'd have to add some `e` transitions. `1-a-2-e-3-b-4-e-5...` With your jumps that I obviously can't do on one line :P – Brandon Buck Nov 29 '11 at 23:06
  • `1-a-2-e-3-b-4-e-5` ? So i would have to add more `e` transitions? – unleashed Nov 29 '11 at 23:17
  • It looks like you need 2-3, otherwise 2 couldn't be skipped. –  Nov 30 '11 at 00:30
  • @sln Node `2` doesn't print `b` Node `1` direct to `2` does, you can draw it as Node `1` skipping to Node `2` and be accurate as well as that path would be marked with `e`. In this case, `e` representing an empty string. – Brandon Buck Nov 30 '11 at 13:48
  • 1
    @unleashed The example you linked was `a*` and it was `1-e-2-a-3-e-4` (with the jumps). I was just pointing out that if that is the correct way your professor (or whomever) wants it done then you'd want to apply that same pattern to the portion of your graph that represents `b*`. – Brandon Buck Nov 30 '11 at 13:49
  • @izuriel yes I agree. Different content online represent NFA repeat in a different way. – unleashed Nov 30 '11 at 18:30
  • 1
    The NFA given is a trivial translation of the regular expression. There are simple algorithms to determinise and minimise finite automata; find them in any basic TCS textbook. Therefore, this question might have been perfect for the upcoming [Computer Science Stack Exchange](http://area51.stackexchange.com/proposals/35636/computer-science-non-programming?referrer=pdx8p7tVWqozXN85c5ibxQ2). So, if you like to have a place for questions like this one, please go ahead and help this proposal to take off! – Raphael Dec 03 '11 at 17:49

1 Answers1

0

Your NFA graph is correct. It will match the regex ab*((b|d)|c*) and nothing else. However, it could be much simpler, e.g. like this:

enter image description here

Staffan Nöteberg
  • 4,095
  • 1
  • 19
  • 17
  • I don't think this is totally correct, the branching portion `((b|d)|c*)` is two branches, not three, It's either (b|d) or c*, so from your `b` node wouldn't it be more accurate to represent that as a fully separate path that then branches into either `b` or `d`? – Brandon Buck Nov 30 '11 at 13:46
  • I'm sure the one above isn't using Thompson construction. It is shorter but I was given a style of how to do it by my lecturer. – unleashed Nov 30 '11 at 18:33
  • @unleashed I'd say that Thompson is an algorithm (a procedure) to create an NFA, not a type of NFAs. You can see my NFA as something created with Thompson and then optimized. (BTW: The question was if your NFA is equivalent to your regular expression. Nothing about Thomspon there :-)) – Staffan Nöteberg Dec 01 '11 at 14:23
  • @izuriel `(b|d)|c*` is equivalent to `b|d|(c*)` in regular expression algebra, isn't it? Kleene closure has higher precedence than Alternation. – Staffan Nöteberg Dec 01 '11 at 14:30
  • @StaffanNöteberg Yea, I see your point. It just threw me off initially but they produce the same result :P – Brandon Buck Dec 01 '11 at 15:41