-2

I have got a problem working on a deterministic finite automaton.

I have got 2 alphabets $\Sigma_a = \{a_1,a_2,a_3...,a_n\}$ and $\Sigma_b = \{b_1,b_2,b_3...,b_n\}$ the automaton should match a alphabet: $\Sigma = \Sigma_a \cup \Sigma_b$ in mathematic: \begin{align} L_a &= \{w ∈ Σ^* \mid \exists\ 1 \leqslant i_1 < i_2 < ... < i_n \leqslant |w| : w_{i_1}w_{i_2} \dotsm w_{i_n} = a\}\\ L_b &= \{w ∈ Σ^* \mid \exists\ 1 \leqslant i_1 < i_2 < ... < i_m \leqslant |w| : w_{i_1}w_{i_2} \dotsm w_{i_m} = b\} \end{align} for example: $a_1,a_2,a_3,b_1,b_2,b_3$ but also $a_1,b_1,a_2,b_2$. the alphabets should be ascending.

I have no idea how do describe this in a mathematic formula. Or even draw the automaton for $|a| = |b| = 3$. I tried it but this automaton has unbelievable many states.

greets.

J.-E. Pin
  • 40,163
student23
  • 1

1 Answers1

0

The automaton for $|a|=|b|=3$ will have 16 states. Picture these states as arranged in a 4x4 square, with the initial state in the top left hand corner. Label each state with its (right,down) co-odinates in the square - so the initial state is labelled $(0,0)$.

In the initial state the automaton can accept $a_1$ or $b_1$. Suppose $a_1$ takes you one place to the right in the 4x4 square to state $(1,0)$, and $b_1$ takes you one place down to state $(0,1)$.

From state $(1,0)$ the automaton can accept $a_2$, going right to state $(2,0)$. Or it can accept $b_1$ going down to state $(1,1)$.

Similarly from state $(0,1)$ the automaton can accept $a_1$, going right to state $(1,1)$. Or it can accept $b_2$ going down to state $(0,2)$.

Note that state $(1,1)$ can be reached in two ways - either input $a_1b_1$ or $b_1a_1$ will take the automaton to state $(1,1)$, In either case the automaton will now accept inputs $a_2$ or $b_2$.

So the automaton is in state $(m,n)$ after it has seen characters $a_1$ to $a_m$ and $b_1$ to $b_n$ (where $m$ or $n$ can be 0), and will now accept inputs $a_{m+1}$ or $b_{n+1}$.

The final state of the automaton is state $(3,3)$ at the bottom right hand corner of the square.

gandalf61
  • 15,326