Considering this FSM: finite state machine

Can someone explain me why the grammar is not:

  1. $S \rightarrow aA$
  2. $A \rightarrow aA \mid bB \mid \varepsilon$
  3. $B \rightarrow bB \mid \varepsilon$

Why does A not have a transition to $\varepsilon$?

  • 1
    $\begingroup$ The grammar given by the FSM and the FSM don't agree. A grammar from the FSM picture would be $S \to \epsilon \mid a A ; A \to \epsilon \mid a A \mid b B ; B \to \epsilon \mid b B$. There are productions to $\epsilon$ for all final states (all in the picture). $\endgroup$ – vonbrand Apr 9 '13 at 19:48
  • $\begingroup$ There is an error in my manual then. Thank you $\endgroup$ – Pier-Alexandre Bouchard Apr 10 '13 at 3:41

Both grammars are wrong: The first does allow String $b$, which is not accepted by the NFA, the second does not allow $\epsilon$, which is accepted by the NFA.

Note that some definitions of regular grammars don't allow renaming of variables, which makes the first grammar irregular. In the same way $\varepsilon$-transitions don't extend the expressive power of NFAs, renaming variables does not extend the expressive power of regular grammars.

So if the automaton is what you want (i.e. ensure that a word which contains a $b$, contains an $a$, too), just add $S \rightarrow \varepsilon$ to your second grammar. If the first grammar is what you want ($\{a\}^*\{b\}^*$) add $S{b \atop \rightarrow }B$ to your automaton and $S \rightarrow \varepsilon\mid bB$ to the second grammar.

  • $\begingroup$ The first one is copy paste of my AI manual.. $\endgroup$ – Pier-Alexandre Bouchard Apr 9 '13 at 18:33
  • $\begingroup$ The first one allows b, because B is double rounded $\endgroup$ – Pier-Alexandre Bouchard Apr 9 '13 at 18:34
  • 1
    $\begingroup$ No: There has to be a path from $S$ only using $b$. $\endgroup$ – frafl Apr 9 '13 at 18:36
  • $\begingroup$ You are right, I think S and A from the automata should not be double rounded, in the first grammar. $\endgroup$ – Pier-Alexandre Bouchard Apr 9 '13 at 18:50
  • $\begingroup$ No, that's fine, since $S\Rightarrow A \Rightarrow B \Rightarrow \varepsilon$. You should an an arc $S{\rightarrow \atop b}B$ or make either $A$ or $B$ an initial state. $\endgroup$ – frafl Apr 9 '13 at 19:19

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.