Regular Grammar to my Regex/DFA

Question

I have following regular expression: ((abc)+d)|(ef*g?)

I have created a DFA (I hope it is correct) which you can see here

http://www.informatikerboard.de/board/attachment.php?attachmentid=495&sid=f4a1d32722d755bdacf04614424330d2

The task is to create a regular grammar (Chomsky hierarchy Type 3) and I don't get it. But I created a regular grammar, which looks like this:

S → aT

T → b

T → c

T → dS

S → eT

S → eS

T → ε

T → f

T → fS

T → gS

Best Regards Patrick

Answer 1

Type 3 Chomsky are the class of regular grammars constricted to the use of following rules:

X -> aY
X -> a,

in which X is an arbitrary non-terminal and a an arbitrary terminal. The rule A -> eps is only allowed if A is not present in any of the right hand sides.

Construction

We notice the regular expression consists of two possibilities, either (abc)+d or ef*g?, our first rules will therefor be S -> aT and S -> eP. These rules allow us to start creating one of the two possibilities. Note that the non-terminals are necessarily different, these are completely different disjunct paths in the corresponding automaton. Next we continue with both regexes separately:

(abc)+ We have at least one sequence abc followed by 0 or more occurrences, it's not hard to see we can model this like this:

S -> aT
T -> bU
U -> cV
V -> aT   # repeat pattern
V -> d    # finish word

ef*g? Here we have an e followed by zero or more f characters and an optional g, since we already have the first character (one of the first two rules gave us that), we continue like this:

S -> eP
S -> e    # from the starting state we can simply add an 'e' and be done with it,
          # this is an accepted word!
P -> fP   # keep adding f chars to the word
P -> f    # add f and stop, if optional g doesn't occur
P -> g    # stop and add a 'g'

Conclusion

Put these together and they will form a grammar for the language. I tried to write down the train of thought so you could understand it.

As an exercise, try this regex: (a+b*)?bc(a|b|c)*