# Simple FSM question

Considering this FSM:

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$?

• 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). – vonbrand Apr 9 '13 at 19:48
• There is an error in my manual then. Thank you – 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.
• No: There has to be a path from $S$ only using $b$. – frafl Apr 9 '13 at 18:36
• 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. – frafl Apr 9 '13 at 19:19