[Solved]: Converting regular (Type-3) grammar to a deterministic finite state automaton

Problem Detail: 

I would like to create a deterministic finite state automaton (DFA) M=(Q, Σ, δ, q0, F) that is accepting the language generated by the following regular grammar (RG) G=(N, Σ, P, S). In short I want to convert RG to DFA.

G = ({S,A,B},{a,b},P,S) P = {  S -> aA | bB, A -> aS | a, B -> bS | b } 

I have found these rules that convert RG to a finite automaton (which might not be deterministic if I think correctly).

1. δ(B, a) = C if B → aC ∈ P 2. δ(B, a) = K if B → a ∈ P    K ∈ F 3. δ(K, *) = emptySet     i.e. q0 ∈ F, if S → ε ∈ P    I dont understand rule 3 

Now I am using these rules on G this way.

A -> aS becomes δ(A, a)=S according to 1st rule  A -> aS becomes δ(A, a)=K according to 2nd rule 

Now I already have

δ(A, a)=S δ(A, a)=K 

which means the automaton is not deterministic because

δ(A, a)={S,K} 

Am I doing something wrong?

Asked By : Slazer

Answered By : Slazer

As Rick Decker said, the algorithm doesnt guarantee that the conversion from G will yieald a DFA. Therefore I should convert to a NFA and than to the DFA. The howto is here.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/40951