CODEWITHSUNDEEP
regular-languagefinite-automata
user3808470
user3808470

Reputation:

Automaton that recognizes a language without 3 consecutive zeros

I would create a finite state automaton that recognizes the language of strings of 0 and 1 that don't contain 3 consecutive zeros. I tried to do the following automaton but isn't complete as, for example, it doesn't recognize the string: 1001110 enter image description here

How can I change it? For the rest, my reasoning to solve the exercise is that correct? Thanks so much

Upvotes: 0

Views: 12741

Answers (2)

Divyesh Jesadiya
Divyesh Jesadiya

Reputation: 957

i made this in paint so not looking nice but,try below automation.enter image description here

Upvotes: 4

David K
David K

Reputation: 3132

Your starting state, q0, is a state that is not reached by reading a zero. As you correctly modeled in your automaton, from the state q0 you must allow the automaton to read up to two zeros, hence you need states q1 (reached by reading exactly one consecutive zero) and q2 (reached by reading exactly two consecutive zeros).

Whenever you read a 1 you will be in a state that was not reached by reading a zero. Now a question is, how many states do you need?

It is permissible to have more than one end state in a finite automaton. In this case you must have more than one end state, because any time you read a 1 you must reach a state that permits two subsequent consecutive zeros to be read, whereas every time you read a zero you much reach a state that does not permit two subsequent consecutive zeros to be read, and your language has strings that end in zero as well as strings that end in 1.

Upvotes: 1

Related Questions