Deriving a regular grammar for the language recognised by the Finite Automata

Question

I'm having trouble figuring out on deriving a regular grammar for a language that is recognised by a Finite Automata. The key issue I'm facing is the confusion between a regular grammar and a context free grammar. I can't seem to distinguish the difference between both of them and i find them very similar in some aspects such as ambiguity.

Could anyone please explain on how to derive a regular grammar for the language recognised by an FA?

Answer 1

When we speak of regular grammars, we might be talking about (strictly) regular grammars or (extended) regular grammars. These distinct concepts correspond more or less exactly to DFAs and to generalized NFAs with empty transitions, respectively.

Furthermore, regular grammars are either right-regular or left-regular. I find right-regular grammars to be altogether easier to think about, but your mileage may vary.

Given a DFA, a (strictly) right-regular grammar can be produced as follows:

1. N = Q; the set of nonterminals of the grammar is the set of states of the DFA.
2. S = q0; the start symbol of the grammar is the initial state of the DFA.
3. P will contain a production X := aY for nonterminals X and Y and alphabet symbol a if and only if there is a transition in the DFA from state X to state Y on input a.
4. P will contain a production X := a for nonterminal X and alphabet symbol a if and only if there is a transition in the DFA from state X to some accepting state on input a.
5. P will contain a production q0 := e if and only if the state q0 is accepting in the DFA.

The above construction attempts to avoid adding unnecessary empty productions. If we don't mind having lots of empty productions, an alternative is to dispense with step 4 and in step 5, add transitions X := e if and only if X is an accepting state. This has the same effect.

Given a generalized NFA with empty transitions, an (extended) right-regular grammar can be produced as follows:

1. N = Q; the set of nonterminals of the grammar is the set of states of the gNFA-e.
2. S = q0; the start symbol of the grammar is the initial state of the gNFA-e.
3. P will contain a production X := wY for nonterminals X and Y and string w over the alphabet if and only if there is a transition in the gNFA-e from state X to state Y on input w.
4. P will contain a production X := e if and only if the state X is accepting in the gNFA-e.

Basically, as in rici's linked answer, regular grammars are just an alternate notation for the same underlying information as is present in finite automata. This is fundamentally different from, say, regular expressions which are a fundamentally different (however equivalent) notation for representing regular languages.