By writing a regular expression or a grammar, describe the language accepted by the NFA

Question

NFA diagram

the strings accepted are aaaaa which is pretty clear. The L = (111 + 1111)* is what I am getting but I need it in regular expression or grammar

Answer 1

NFA State Diagram:
     a       a     a 
q0i---->q1---->q2---->q3f
^^             |      |
||     a       |      |
||--------------      |
|         a           |
|----------------------


Transition Equations (NFA ==>DFA):                      
f(q0,a) = q1
f(q1,a) = q2
f(q2,a) = {q0,q3}f
f(q3,a) = q0
f({q0,q3},a) = {q0,q1}
f({q0,q1},a) = {q1,q2}
f({q1,q2},a) = {q0,q2,q3}f
f({{q0,q2,q3},a) = {q0,q1,q3}f
f({q0,q1,q3},a) = {q0,q1,q2}
f({q0,q1,q2},a) = (q0,q1,q2,q3}f
f((q0,q1,q2,q3},a) = {q0,q1,q2,q3}f


DFA State Diagram:
     a      a      a           a            a          a                a               a              a
q0i---->q1---->q2---->{q0,q3}f---->{q0,q1}---->{q1,q2}---->{q0,q2,q3}f---->{q0,q1,q3}f---->{q0,q1,q2}---->(q0,q1,q2,q3}f
                                                                                                                 | |
                                                                                                                  ->
                                                                                                                   a


Basic Regular Expression (in unix grep format):
^aaa\(\(aaa\(a\(aaa*\)\?\)\?\)\?\)\?$


Manual Tests:
# of a's  NFA  DFA
1         n    n
2         n    n
3         y    y
4         n    n
5         n    n
6         y    y
7         y    y
8         n    n
9         y    y
10        y    y
11        y    y
12        y    y


Unix grep Tests:
Mac_3.2.57$echo a | grep '^aaa\(\(aaa\(a\(aaa*\)\?\)\?\)\?\)\?$'
Mac_3.2.57$echo aa | grep '^aaa\(\(aaa\(a\(aaa*\)\?\)\?\)\?\)\?$'
Mac_3.2.57$echo aaa | grep '^aaa\(\(aaa\(a\(aaa*\)\?\)\?\)\?\)\?$'
aaa
Mac_3.2.57$echo aaaa | grep '^aaa\(\(aaa\(a\(aaa*\)\?\)\?\)\?\)\?$'
Mac_3.2.57$echo aaaaa | grep '^aaa\(\(aaa\(a\(aaa*\)\?\)\?\)\?\)\?$'
Mac_3.2.57$echo aaaaaa | grep '^aaa\(\(aaa\(a\(aaa*\)\?\)\?\)\?\)\?$'
aaaaaa
Mac_3.2.57$echo aaaaaaa | grep '^aaa\(\(aaa\(a\(aaa*\)\?\)\?\)\?\)\?$'
aaaaaaa
Mac_3.2.57$echo aaaaaaaa | grep '^aaa\(\(aaa\(a\(aaa*\)\?\)\?\)\?\)\?$'
Mac_3.2.57$echo aaaaaaaaa | grep '^aaa\(\(aaa\(a\(aaa*\)\?\)\?\)\?\)\?$'
aaaaaaaaa
Mac_3.2.57$echo aaaaaaaaaa | grep '^aaa\(\(aaa\(a\(aaa*\)\?\)\?\)\?\)\?$'
aaaaaaaaaa
Mac_3.2.57$echo aaaaaaaaaaa | grep '^aaa\(\(aaa\(a\(aaa*\)\?\)\?\)\?\)\?$'
aaaaaaaaaaa
Mac_3.2.57$echo aaaaaaaaaaaa | grep '^aaa\(\(aaa\(a\(aaa*\)\?\)\?\)\?\)\?$'
aaaaaaaaaaaa