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
Pingback: Automata Practice Questions | Usman's Blog