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! screenshot

  • $\begingroup$ Something is broken with your image link. Did you know that you can include the image in the post? $\endgroup$ – Dave Clarke Apr 4 '13 at 19:03
  • $\begingroup$ The image is broken but the entire automaton is readable. $\endgroup$ – saadtaame Apr 4 '13 at 19:26
  • $\begingroup$ 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. $\endgroup$ – Raphael Apr 4 '13 at 23:30
  • $\begingroup$ Added the image (which I created in dot format. I wish I could just add the dot source: meta.stackexchange.com/questions/70933/…) $\endgroup$ – reinierpost Apr 5 '13 at 11:27

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$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy