patternMinor
Finite state automata, multiple completion states?
Viewed 0 times
completionfinitestatesautomatastatemultiple
Problem
I'm currently studying for an exam for a course where some of the material covered included finite state automata, I've completed a question and I'm not sure about my answer.
Exercise
Explain what is meant by a Finite State Automaton (FSA) by drawing an FSA to recognise strings of the form $a^rb^s$, where $r\gt0$ and $s\ge0$ and with an alphabet of $\{a,b\}$, i.e., there must be at least one $a$, zero or more $b$'s and all occurrences of $a$ must precede any occurrence of $b$. Illustrate, how your FSA works given the following sample strings:
$\quad$(i) $abbb$
$\quad$(ii) $aaaa$
$\quad$(iii) $aba$
My Answer
Are multiple completion states allowed?
Exercise
Explain what is meant by a Finite State Automaton (FSA) by drawing an FSA to recognise strings of the form $a^rb^s$, where $r\gt0$ and $s\ge0$ and with an alphabet of $\{a,b\}$, i.e., there must be at least one $a$, zero or more $b$'s and all occurrences of $a$ must precede any occurrence of $b$. Illustrate, how your FSA works given the following sample strings:
$\quad$(i) $abbb$
$\quad$(ii) $aaaa$
$\quad$(iii) $aba$
My Answer
Are multiple completion states allowed?
Solution
Your DFA is close, but not quite right. Note that the description requires the strings in the language to have at least one $a$, whereas your DFA will accept the empty string. The fix is simple of course:
And yes, having multiple accept states is fine (in fact, some languages require it).
And yes, having multiple accept states is fine (in fact, some languages require it).
Context
StackExchange Computer Science Q#6934, answer score: 5
Revisions (0)
No revisions yet.