0

I have this regular expression

[A-E]|[A-E]{3}|[A-E]{4} 

[A-E]|[A-E] [A-E] [A-E]|[A-E][A-E][A-E] [A-E]

it recognizes strings of A,B, ABC, BCD, BCDE, etc.

I want to construct the NFA but have no idea if i am correct

  1. I have done this http://s1.postimg.org/627870q8v/image.png

  2. or this

http://s10.postimg.org/sqbxf2t5l/image.png

Which one is correct ?

my [A-E] NFA is

http://s17.postimg.org/4b0q1w1mn/image.png

Raman photografar
  • 3
  • 1
Vasileios Kougioumtzis
  • 78
  • 1
  • 8
  • I'd say #2 is clearer, but they both look right. – Reinstate Monica -- notmaynard Apr 22 '13 at 14:25
  • What concerns me is the flow of the second one , Lets say the user inputs ABCD , In the first we have A->B->C->D ->Final But in the second NFA how can we determine which route should take, if A for example goes to the first it succeeds... but the correct is to have both ABCD into the third route of [A-E]{4}... – Vasileios Kougioumtzis Apr 22 '13 at 14:32

1 Answers1

1

The minimal DFA is the following

0 -> 1 -> 2 -> 3 -> 4

with every transition arch signed by [A-E] and with final states = {1,3,4}

In fact this DFA is equivalent with both your NFA. Nevertheless I find the second to be clearer.

5agado
  • 2,444
  • 2
  • 21
  • 30
  • Also how can we make the expression in such way so it cant recognize inputs of double letters, example "ABC" is acceptable BUT "AAC" is not the expression is meant to describe, angles (A), or triangles (ABC), or rectangles (ABCD) , so AACB is must be rejected as a name of rectangle or be analyzed as A(angle) , ACB(triangle) but not AACB.... – Vasileios Kougioumtzis Apr 22 '13 at 14:49
  • In the simplest case (ordered letters) a linear automaton is enough (all final states except for the first). But if you want to recognize all the permutations is a little bit harder. I'm not an expert, but maybe for this case is better to define a suitable Grammar. Give a look [Here](http://stackoverflow.com/questions/10332894/) for a regex point of view of the problem. – 5agado Apr 22 '13 at 15:06