Problem Set 9

DFAs

1 DFA to Language

Determine whether or not the following are valid DFA definitions. If the DFA is valid, what is the language of the DFA?

1.1

Solution

Not valid - the top state has no outgoing 0 transition.

1.2

Solution Every 0 is followed by a 1.

1.3

Solution

Doesn’t contain 10

2 Language to DFA

2.1

Find a DFA/NFA for the following languages:

  • \(L_1 = \{w \in \{0,1\}^* : w \text{ is a binary representation of a multiple of 3}\}\). Find a DFA for \(L_1\).

  • \(L_2 = \{w \in \{0,1\}^* : \text{every 1 is preceeded by at least two zeros }\}\).

  • \(L_3 = \{w \in \{0,1\}^* : \text{every 1 is preceeded by at exactly two zeros }\}\).

  • \(L_4 = \{w \in \{0,1\}^* : \text{every 1 is preceeded by at most two zeros }\}\).

  • \(L_5 = \{w \in \{0,1\}^* : \text{w contains neither 01 nor 10}\}\).

Solution

Link