FSMs

Computer Science Level 1

Which string will not be accepted by the finite state machines below?

https://en.wikibooks.org/wiki/File:CPT-FSM-01.svg https://en.wikibooks.org/wiki/File:CPT-FSM-01.svg

101 100110 1000001 1110001

View wiki
Karleigh Moore by Karleigh Moore , 27, USA

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Karleigh Moore
Jun 21, 2016

This FSM doesn't accept strings that end in 0's. The other options will be accepted. You can verify this for yourself by tracing through the diagram — each of the other options has a valid path from the start state to the accept state.

25 Helpful 1 Interesting 0 Brilliant 3 Confused

I'm unfamiliar with the syntax of the shapes; is S3 the accept state? And is the start state, S1, also an accept state?

Adam Becerra - 2 years, 3 months ago

Answered my own question: the accept state is the double-ringed state, S3, and the string must end up there to be part of the regular language for this FSM. The FSM accepts strings with any number of 1s ending with an odd number of 0s followed by a 1.

Adam Becerra - 2 years, 3 months ago
Pournima Kute
Mar 3, 2021

Only the transitions that end on a final state are accepted. Option B. does not seem to end in the final state. Hence, not accepted. Others do.

0 Helpful 0 Interesting 1 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...