2
$\begingroup$

Statement:

Given any dfa $M$, application of the procedure 'reduce' (see below) yields another dfa $\hat{M}$ such that $M$ and $\hat{M}$ are equivalent. Furthermore $\hat{M}$ is minimal in the sense that there is no other dfa with a smaller number of states that also accepts $L(M)$

First some background information:

The 'reduce' procedure:

Given a dfa $M=\left(Q, \Sigma, \delta, q_{0}, F\right)$, we construct a reduced dfa $\widehat{M}=(\widehat{Q}, \Sigma, \widehat{\delta}, \widehat{q}, \widehat{F})$ as follows.

  1. Use procedure mark to generate the equivalence classes, say $\left\{q_{i}, q_{j}, \ldots, q_{k}\right\}$, as described.
  2. For each set $\left\{q_{i}, q_{j}, \ldots, q_{k}\right\}$ of such indistinguishable states, create a state labeled $i j \ldots k$ for $\widehat{M}$.
  3. For each transition rule of $M$ of the form $$ \delta\left(q_{r}, a\right)=q_{p}, $$ find the sets to which $q_{r}$ and $q_{p}$ belong. If $q_{r} \in\left\{q_{i}, q_{j}, \ldots, q_{k}\right\}$ and $q_{p} \in\left\{q_{l}, q_{m}, \ldots, q_{n}\right\}$, add to $\widehat{\delta}$ a rule $$ \widehat{\delta}(i j \cdots k, a)=l m \cdots n . $$
  4. The initial state $\widehat{q}_{0}$ is that state of $\widehat{M}_{\text {}}$ whose label includes the 0 .
  5. $\widehat{F}$ is the set of all the states whose label contains $i$ such that $q_{i} \in F$.

A claim in order to prove the statement:

Take any state $q \in Q$ and let $\hat{q}$ denote its equivalence class. For any word $w \in \Sigma^{*}$, it holds that $\delta^{*}(q, w) \in \hat{\delta}^{*}(\hat{q}, w)$. The proof is by induction on the length $n$ of $w$. base case If $n=0$, then $w=\lambda$ and the claim is trivial since $$ \delta^{*}(q, \lambda)=q \in \hat{q}=\hat{\delta}^{*}(\hat{q}, \lambda) . $$ For the induction step assume our claim holds for all strings of length $n-1$ we show that it shows for strings of length $n$. In this case $w=a v$ for some $v$. We know that $$ \begin{array}{rlr} \delta^{*}(q, w) & =\delta^{*}(q, a v) \\ & =\delta^{*}(\delta(q, a), v) & \text { definition of } \delta^{*} \\ & \in \hat{\delta}^{*}(\widehat{\delta(q, a)}, v) & \text { induction hypothesis } \\ & =\hat{\delta}^{*}\left(\hat{\delta}^{}(\hat{q}, a), v\right) \\ & =\hat{\delta}^{*}(\hat{q}, w) \\ \end{array} $$

My question:

In the proof of the claim above, I do not know how we can be sure that

$ \widehat{\delta(q, a)} = \hat{\delta}^{}(\hat{q}, a)$

It seems trivial, but shouldn't it be proven?

Source: Formal languages and automata by Peter Linz, 5th edition (Jones & Bartlett Learning), p. 75

$\endgroup$
2
  • 1
    $\begingroup$ Books have authors and publishers. They often go through multiple editions, each with a date. Quotes are taken from a particular page in a particular edition of a particular book, and a citation must include this information. I guessed which book you're talking about, but you need to fill in the rest. This is mandatory, not just by the rules of this site, but also to comply with copyright rules and academic practice. Thanks. $\endgroup$
    – rici
    Aug 27 at 22:58
  • $\begingroup$ @rici I updated the question, thank you for the feedback. $\endgroup$
    – Ronald
    Aug 30 at 9:32

1 Answer 1

2
$\begingroup$

$ \widehat{\delta(q, a)} = \hat{\delta}^{}(\hat{q}, a)$

The equality above is the definition of $\hat\delta$, given $\delta$. Let us paraphrase item 3.

  1. For each transition rule of $M$ of the form $$ \delta(q, a)=\delta(q, a), $$ find the sets to which $q$ and $\delta(q, a)$ belong. If $q \in\hat q$ and $\delta(q, a)\in\widehat{\delta(q, a)} $, add to $\widehat{\delta}$ a rule $$ \hat{\delta}(\hat q, a)= \widehat{\delta(q, a)}. $$

On the other hand, there is an important question: why is $\delta$ well-defined? Suppose $q_i\in \hat q$ and $q_j\in \hat q$, then $\hat{\delta}(\hat q, a)$ is defined as $\widehat{\delta(q_i,a)}$ as well as $\widehat{\delta(q_j,a)}$. Are $\widehat{\delta(q_i,a)}$ and $\widehat{\delta(q_j,a)}$ the same equivalence class?

This well-defined-ness is a key step in the 'reduce' procedure. I will leave it for you to verify.

$\endgroup$
3
  • $\begingroup$ Thank you very much! About the question in your answer: Suppose that the transitions resulted in different equivalence classes, that would mean that δ(qi,a) and δ(qj,a) are distinguishable. Suppose they are distinguishable by a string of length n, then qi and qj would be distinguishable by a string of length n+1 and so they wouldn’t be in the same equivalence class (contradiction). Is this a correct reasoning and answer to the question? $\endgroup$
    – Ronald
    Aug 31 at 10:17
  • $\begingroup$ And I can't edit the answer because my edit is too small, but I think you made a little mistake in the question: "is defined as ˆδ(qi,a) as well as ˆδ(qi,a)" so two times qi instead of qi and qj. $\endgroup$
    – Ronald
    Aug 31 at 10:20
  • $\begingroup$ Yes, that is correct. $\endgroup$
    – John L.
    Aug 31 at 13:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.