Menu Close

What language (or set of strings) is accepted by the following DFA?

Described as a list of strings:

{ “01”, “111”, “0011”, “01111”, “10”, “000”, “0110”, “1111”, “00111”,

“011111”…}

where all underlined strings may have any number of 0s appended

Described as a regular expression: 01 | (1 | 00 | 011)(11 | (0 | 111)0*)

Explanation (for each underlined portion of RE)

  • 01 | (1 | 00 | 011)(11 | (0 | 111)0*) from state 1 to 5 and accepts
  • 01 | (1 | 00 | 011)(11 | (0 | 111)0*) from state 1 to 2, then…
  • 01 | (1 | 00 | 011)(11 | (0 | 111)0*) from state 2 to 7 and accepts
  • 01 | (1 | 00 | 011)(11 | (0 | 111)0*) from state 2 to 3, then…
  • 01 | (1 | 00 | 011)(11 | (0 | 111)0*) accepts w/ 0 or more 0’s

1 Comment

  1. Pingback: Automata Practice Questions | Usman's Blog

Leave a Reply

Your email address will not be published. Required fields are marked *