Giving a regular grammar for the language

Question

I am trying to brush up on my regular grammar knowledge to prepare for an interview, and I just am not able to solve this problem at all. This is NOT for homework, it is merely me trying to solve this.

I want to give a regular grammar for the language of the finite automaton whose screen shot is below, please help me, and if you can, a step by step answer would be of great assistance. Thank you!

Answer 1

To convert an automaton to a regular grammar is easy. You have one symbol for each state of the automaton, in this case $A, B,$ and $C$. Each symbol has one production for each transition that the automaton has out of the corresponding state. For example, when you have a transition $A\stackrel{0}{\to} B$ as you do here, the corresponding production is $A\to 0B$.

Then you let the start symbol be $S$, and add a single production $S\to A$, where $A$ is the start state. And for each accepting state, say $C$, you add a production $C\to\epsilon$.

So the solution here is:

$$\begin{align} S & \to A\\ A & \to 1A \mid 0B\\ B & \to 1A \mid 0C\\ C & \to 1C \mid 0C \mid \epsilon \end{align} $$

The idea here is that the grammar symbol $B$ can produce all the strings that the automata would accept as input from state $B$. Since $B$ has a transition on 0 to state $C$, the $B$ symbol should be able to produce any string that has a 0 followed by some string that would be accepted from state $C$, so we add a production $B\to 0C$ so that the $B$ symbol can produce such strings.

Then in accepting states, the automaton will accept $\epsilon$, so we add those productions too.

Answer 2

If you have a finite automaton for a regular language $L$, you can construct a right regular grammar for $L$ directly from the automaton, by using the states as the variables and the alphabet as the terminals and essentially just writing down the transition function in the form of productions.

So for your automaton, you would start with the transitions $A\to 1A$ and $A\rightarrow 0B$. (Except you would usually rename $A$ to $S$, because it's traditional to use $S$ for the start symbol.) You'll learn more by finishing the example for yourself, so I'll leave it at that for now, but feel free to ask for more help if you need it.