1

The question goes like this: Design a finite state automaton that accepts binary strings with at least two $0$s and at most two $1$s.

I can easily design an NFA which accepts at least two $0$s OR at most two ones.

Additional question, how do you write regular expressions for automatas like these?

I cant get this method to work to generate regular expressions.

EDIT: Here is a photo of the solution. https://i.stack.imgur.com/CxLDU.jpg

EDIT 2: In the photo S5 will have a 0 to itself and S8 is the accepting state.

Community
  • 1
Souradeep Nanda
  • 273
  • Additional question, how do you write regular expressions for automatas like these?

    an answer : a backward transition must be a $\ast$ in the regular expression, so you can see it's complicated

     – reuns Jul 20 '15 at 16:31
  • Once I got the FSM, I was able to get the regular expression using the same method. Thanks anyways. – Souradeep Nanda Jul 21 '15 at 02:56

2 Answers2

3

Use an automaton with the following states

  • Have seen no 0 and no 1
  • Have seen one 0 and no 1
  • Have seen at least two 0 and no 1
  • Have seen no 0 and one 1
  • Have seen one 0 and one 1
  • Have seen at least two 0 and one 1
  • Have seen no 0 and two 1
  • Have seen one 0 and two 1
  • Have seen at least two 0 and two 1
  • Have seen at least three 1

with the obvious transitions and accepting states among these.

Hagen von Eitzen
  • 374,180
0

The general idea to simulate two finite automata running at once, here independent counting processes with

  • $Q_1$: $3$ states for counting digit $0$: counted $0$, $1$, $2$ or more digits
  • $Q_2$: $4$ states for counting digit $1$: counted $0$, $1$, $2$, $3$ or more digits

is to construct the product states $Q_1 \times Q_2$ and the product automaton, as demonstrated by Hagen's solution.

mvw
  • 34,562