Take the 2-minute tour ×

I have this regular expression


[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


Which one is correct ?

my [A-E] NFA is


share|improve this question
I'd say #2 is clearer, but they both look right. –  iamnotmaynard 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}... –  Vasilis Apokapa Apr 22 '13 at 14:32

1 Answer 1

up vote 1 down vote accepted

The minimal DFA is the following


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.

share|improve this answer
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.... –  Vasilis Apokapa 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 for a regex point of view of the problem. –  5agado Apr 22 '13 at 15:06

Your Answer


