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.

Answer 2

The way I understand it is that CFLs are a good way for describing infinite sets in a finite way and also for describing the syntax of languages.

CFLs and regular languages... All regular languages are context free, but not necessarily vice versa. Why?

We can prove this by using the pumping lemma, and pumping on the Context Free Language described by {a^n b^n | n ≥ 0} to show that it is not regular but it is a CFL because it is generated by the grammar G = (V, Σ, R, Start) where:

• V: a finite set of variables or nonterminals E.g V = {S}
• Σ: a finite set which is disjoint from V, called the alphabet or terminals E.g Σ = {a,b}
• R: is a set of production rules with each rules E.g R = {S → aSb, S → ε}
• S: the start variable E.g Start = {S}

Note that a string w is derived ambiguously in a context-free grammar G if it has two or more different leftmost derivations. A grammar G is ambiguous if it generates some string ambiguously and sometimes, when we have an ambiguous grammar, we can find an unambiguous grammar that generates the same language. Note that some context-free languages can only be generated by ambiguous grammars - known as inherently ambiguous.

Also, any context-free language is generated by a context-free grammar in Chomsky Normal Form. To check whether a string is part of a CFL we can use the Cocke-Younger-Kasami algorithm.

A good read is Sipser, M. (2006). Introduction to the Theory of Computation (Vol. 2). Boston: Thomson Course Technology.