I would like to create a deterministic finite state automaton (DFA) M=(Q, ?, ?,
ID: 647388 • Letter: I
Question
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?
Explanation / Answer
The way I interpret your rules (other than 1 and 2) is:
There is a state K, not corresponding to a non-terminal of the grammar, such that K ? F.
Then rule 3 means that there is no transition from state K, so that any further input when you are in state 3 results in rejection of the input string. The star * means any input, and the empty set says that any input will get you in no state, hence failure unless you have no input left.
The initial state q0 is S, and it belongs also to the set F of final states iff S ? ? ? P
Thus the set F of final states contains either only the state K or the two states S and K.
But as you remark, this gives you in general a NFA, a non-deterministic finite automaton.
To transform it into DFA, you need to apply the so-called powerset construction, that you will find in any textbook on finite automata, and in many other places, including wikipedia.