patternMinor
The transition function of the union of regular languages
Viewed 0 times
thelanguagesunionregularfunctiontransition
Problem
I follow Michael Sipser's book, "Introduction to the Theory of Computation".
To be specific, I am trying to understand the proof about the union of regular languages. However, I have a problem grasping how exactly the transition function is defined.
The book says that for each $(r_1, r_2) \in Q$ and each $a \in\sum$, let
$\delta((r_1, r_2),a) = (\delta_1(r_1, a), \delta_2(r_2,a))$. The problem is that I cannot understand what happens if, for example, $\delta_2(r_2,a) = \emptyset$ and $\delta_1(r_1, a) = q_1$ and I get $\delta((r_1, r_2),a) = (q_1, \emptyset)$, which does not belong to the set of all pairs of states.
To be specific, I am trying to understand the proof about the union of regular languages. However, I have a problem grasping how exactly the transition function is defined.
The book says that for each $(r_1, r_2) \in Q$ and each $a \in\sum$, let
$\delta((r_1, r_2),a) = (\delta_1(r_1, a), \delta_2(r_2,a))$. The problem is that I cannot understand what happens if, for example, $\delta_2(r_2,a) = \emptyset$ and $\delta_1(r_1, a) = q_1$ and I get $\delta((r_1, r_2),a) = (q_1, \emptyset)$, which does not belong to the set of all pairs of states.
Solution
In the definition of a deterministic finite automaton, we require that the transition function $\delta$ is well defined on all of $Q\times\Sigma$, i.e. $\delta: Q\times \Sigma\rightarrow Q$. Sometimes we allow omitting transitions, and say that the automaton is "stuck" if it stumbles upon this transition, however in Sipser's book he defines the transition function as above (defined on all of $Q\times\Sigma$).
If you insist on allowing the the automaton to get stuck, then this results in a slight modification of the proof. Instead of looking at $Q_1\times Q_2$ (where $Q_i$ is the state set of the $i'th$ automaton), consider the state space
$\left(Q_1\cup\left\{\widehat{q_1}\right\}\right)\times\left(Q_1\cup\left\{\widehat{q_2}\right\}\right)$, where $\widehat{q_1},\widehat{q_2}$ are special states designed to deal with lack of transition. You can now complete the details yourself.
If you insist on allowing the the automaton to get stuck, then this results in a slight modification of the proof. Instead of looking at $Q_1\times Q_2$ (where $Q_i$ is the state set of the $i'th$ automaton), consider the state space
$\left(Q_1\cup\left\{\widehat{q_1}\right\}\right)\times\left(Q_1\cup\left\{\widehat{q_2}\right\}\right)$, where $\widehat{q_1},\widehat{q_2}$ are special states designed to deal with lack of transition. You can now complete the details yourself.
Context
StackExchange Computer Science Q#64848, answer score: 4
Revisions (0)
No revisions yet.