Considering this FSM:
Can someone explain me why the grammar is not:
- $S \rightarrow aA$
- $A \rightarrow aA \mid bB \mid \varepsilon$
- $B \rightarrow bB \mid \varepsilon$
Why does A not have a transition to $\varepsilon$?
$\begingroup$
$\endgroup$
2
-
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
Add a comment
|
$\begingroup$
$\endgroup$
5
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
