Transition diagram for DFA's.

636 Views Asked by At

I have a homework question that asks to draw the transition diagram for the following:

Draw transition diagrams for the DFAs below for the following languages. The alphabet Σ in this example is {0,1}.

1) {p001q | p,q ∈ Σ*}.

2) {λ} ---> λ is an empty string.

The questions I have are, for question 1, will p and q take different values? What I mean is, since different variables are used, does that mean the DFA will only accept strings where and first and last value are different, and the 3 middle values must be 001?

And for question 2, I think this will just be one accepting state that has one loop back to itself.

1

There are 1 best solutions below

2
On

The first question has been dealt with in the comments.

The DFA with a single state and transitions that loop at that state treats every $w\in\Sigma^*$ identically: if the state is an acceptor state, it accepts every word in $\Sigma^*$, and if the state is not an acceptor state, it accepts no word at all. Thus, you get either $\Sigma^*$ or $\varnothing$, not $\{\lambda\}$.

To get $\{\lambda\}$, you need to be able to distinguish between empty input and non-empty input; this requires a minimum of two states. If $q_0$ is your initial state, you need another state $q_1$. Clearly $q_0$ should be an acceptor state, so that you accept the empty word, and any other input at all must take you out of $q_0$. Thus, you want transitions

$$q_0\overset{0,1}\longrightarrow q_1\;.$$

Moreover, once you get to $q_1$, you never want to return to $q_0$, so you also want transitions

$$q_1\overset{0,1}\longrightarrow q_1\;.$$

In short, $q_1$ is a non-accepting trap state – what I often call the garbage state.