# Giving a regular grammar for the language

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 screenshot is below, please help me, and if you can, a step by step answer would be of great assistance. Thank you!

• Something is broken with your image link. Did you know that you can include the image in the post? – Dave Clarke Apr 4 '13 at 19:03
• The image is broken but the entire automaton is readable. – saadtaame Apr 4 '13 at 19:26
• What have you tried? You have to have some thoughts. Note that there is an algorithm for converting automata into grammars (or regular expressions); you can find it in any textbook. – Raphael Apr 4 '13 at 23:30
• Added the image (which I created in dot format. I wish I could just add the dot source: meta.stackexchange.com/questions/70933/…) – reinierpost Apr 5 '13 at 11:27

## 1 Answer

That's fairly easy. Just take a non-terminal X and add the rule $X\to aY$ where $a$ is the label on the arrow from $X$ to $Y$ if $X$ is not final; if it's final add a rule like: $X\to \epsilon$ as well. Do that for every non-terminal and you get a right-regular grammar.

Here is a right-regular grammar for the given automaton:

$A \to 1 A$

$A \to 0 B$

$B \to 1 A$

$B \to 0 C$

$C \to 0 C$

$C \to 1 C$

$C \to \epsilon$

• Don't forget to add rules $X \rightarrow a$ if from $X$ you go to a state that is final. – vonbrand Apr 4 '13 at 19:15
• @vonbrand Yes, thank you. It should be $X\to \epsilon$ if $X$ is final. But yours is correct also. – saadtaame Apr 4 '13 at 19:21