Intersection of two deterministic finite automata?

Question

I'm trying to solve a problem where I have to create a DFA for the intersection of two languages.

These are: $$\{s \in \{{\tt a}, {\tt b},{\tt c}\}^\ast : \mbox{every ${\tt a}$ in $s$ is immediately followed by a ${\tt b}$}\}$$

and

$$\{s \in \{{\tt a}, {\tt b},{\tt c}\}^\ast : \mbox{every ${\tt c}$ in $s$ is immediately preceded by a ${\tt b}$}\}$$

I think I am on the right track, but not sure if it is totally correct. Could someone have a look please?

Answer 1

There is a systematic way for creating automatons for intersection of languages. Let $A$ and $B$ be the input automatons. The states of new automaton will be all pairs of states of $A$ and $B$, that is $S_{A\cap B} = S_A \times S_B$, the initial state will be $i_{A \cap B} = \langle i_A, i_B \rangle$, where $i_A$ and $i_B$ are the initial states of $A$ and $B$, and $F_{A\cap B} = F_A \times F_B$ where $F_X$ denotes the set of accepting states of $X$. Finally, the transition function $\delta_{A \cap B}$ is defined as follows for any letter $\alpha \in \Sigma$ and states $p_1, p_2 \in S_A$, $q_1, q_2 \in S_B$:

$$ \langle p_1, q_1 \rangle \xrightarrow[A \cap B]{\ \alpha\ } \langle p_2, q_2 \rangle \quad \text{ iff } \quad p_1 \xrightarrow[A]{\ \alpha\ } p_2 \quad \text{and} \quad q_1 \xrightarrow[B]{\ \alpha\ } q_2 $$

Please note, that such automaton usually is not minimal (e.g. the intersection might be just an empty language). Also it might be useful (but it is not necessary) to make input automatons minimal since the output is quadratic in size.

Hope that helps ;-)

Answer 2

In first and second automaton, you can join states "0" and "2". The automata are correct, but not minimal.

In third automaton, arrows $00 \to 01$ and $01 \to 12$ have no label. Additionally, it seems it will not accept "abcbc".

Answer 3

sdcvvc has already noted some problems with your solution, and dtldarek has given a systematic approach to such problems. I’ll suggest how you could simply have built the desired DFA from scratch in this relatively simple case.

If you want to build the DFA from scratch, you want to make sure that every $a$ is immediately followed by a $b$ and every $c$ is immediately preceded by a $b$. At each state, therefore, you need to know two things: was the last input an $a$ (because then the next must be a $b$), and was the last input a $b$ (so that the next could be a $c$). This suggests that I should start with four states, say $s_0,s_a,s_b$, and $s_c$, with the idea that I’m in state

$$\begin{align*} &s_0\text{ initially,}\\ &s_a\text{ if the last input was }a,\\ &s_b\text{ if the last input was }b,\text{ and}\\ &s_c\text{ if the last input was }c\;. \end{align*}$$

What transitions do I then need?

If I’m in $s_a$, the only acceptable input is $b$, so I want $s_a\stackrel{b}\longrightarrow s_b$; with your convention there are no $s$ or $c$ transitions out of $s_a$. (I would have a ‘dump’ non-acceptor state $s_d$ with transitions $s_d\stackrel{a,b,c}\longrightarrow s_d$ and then have transitions $s_a\stackrel{a}\longrightarrow s_d$ and $s_a\stackrel{c}\longrightarrow s_d$.)

If I’m in $s_b$, every input is acceptable, and I need transitions $s_b\stackrel{a}\longrightarrow s_a$, $s_b\stackrel{b}\longrightarrow s_b$, and $s_b\stackrel{c}\longrightarrow s_c$.

If I’m in $s_c$, only $s_c\stackrel{a}\longrightarrow s_a$ and $s_c\stackrel{b}\longrightarrow s_b$ are wanted: $c$ is an unacceptable input.

Finally, if I'm in $s_0$, only $s_0\stackrel{a}\longrightarrow s_a$ and $s_0\stackrel{b}\longrightarrow s_b$ are wanted: $c$ is an unacceptable input. Evidently I can combine $s_0$ and $s_c$ into a single state, which I’ll call $s_c$. The transition table for the resulting DFA is:

$$\begin{array}{c|cc} &a&b&c\\ \hline s_a&&s_b&\\ s_b&s_a&s_b&s_c\\ s_c&s_a&s_b\\ \end{array}$$

---

A note on the construction described by dtldarek: You should think of it as a way of making one DFA imitate two simultaneously. When you’re in state $s$ in the first automaton and state $t$ in the second, you’re in state $\langle s,t\rangle$ in the new one. The transitions in the new automaton mimic those of the first automaton in the way they treat the first state coordinate, and they mimic those of the second automaton in the way they treat the second state coordinate. It’s a very useful construction. Suppose that you have DFA’s that accept the languages $L_1$ and $L_2$. Depending on how you choose the acceptor states, you can use this construction to get a DFA accepting $L_1\cap L_2$ (as in this problem), a DFA accepting $L_1\cup L_2$, or a DFA accepting $L_1\setminus L_2$.

Answer 4

The easiest thing to do is to create a NFA that accepts the intersection of the two languages. I say easier, because we are allowed to use epsilon $\epsilon$ transitions. Then reduce the NFA to a DFA using something like the powerset construction:

http://en.wikipedia.org/wiki/Powerset_construction

Sometimes, when there are too many states its difficult to try to do it by hand directly.

Also, keep in mind the intersection simply means both automata have to accept the string.