[Solved]: How to draw a DFA for given language?

Problem Detail: 

Give a finite state diagram for a DFA that accepts any word in the language $L = \{w \mid w \in \{a, b\}^* \text{ and }w \text{ alternates } a\text{'s and }b\text{'s and has an even number of }b\text{'s}\}$.

My attempt: I am having problem on how to deal with the even part of b.

Asked By : max

Answered By : Rick Decker

Since the strings must be of the form $ababab\dotsm$, and also there must be 0, 2, 4, 6, ... $b$s, begin with four states, each of which "remembers" the input so far:

• $q_0$: just saw an $a$ and have seen an even number of $b$s so far,
• $r_0$: just saw a $b$ and have seen an odd number of $b$s so far,
• $q_1$: just saw an $a$ and have seen an odd number of $b$s so far,
• $r_1$: just saw a $b$ and have seen an even number of $b$s so far.

Then, it's clear that these states will have transitions in a cycle, with transitions:

• $\delta(q_0, b) = r_0$
• $\delta(r_0, a) = q_1$
• $\delta(q_1, b) = r_1$
• $\delta(r_1, a) = q_0$

and the other possibilities will either be undefined or lead to a trap state, depending on what model of a DFA you're accustomed to using. Now make a new start state $s$, with $\delta(s, a) = q_0$ (since you've just seen an $a$ and have no $b$s yet), and, for similar reasons, define $\delta(s, b) = r_0$. I'll leave it to you to decide which (two) of the states in the cycle of four states should be final.

There are systematic ways to do this kind of product DFA, but in this case, it's no simpler than this ad hoc construction.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/50112

3.2K people like this

 Download Related Notes/Documents