Lemma 13.6    $p \in F \Longleftrightarrow [p] \in F'$

Proof. The direction $\Rightarrow$ is immediate from the definition of $F'$. For the direction $\Leftarrow$, we need to show that if $p \approx q$ and $p \in F$, then $q \in F$. In other words, every $\approx$-equivalence class is either a subset of $F$ or disjoint from $F$. This follows immediately by taking $x = \epsilon$ in the definition of $p \approx q$. $\quad\square$

The excerpt above found in Dexter C. Kozen's Automata and Computability. This lemma is found in a proof of the Quotient Construction for DFA.

I do not understand how the author concludes that if one wants to show $[p] \in F' \implies p \in F$ (1), then it is equivalent to showing that $p≈q$ and $p \in F \implies q \in F$ (2). Can someone please provide as detailed as possible an explanation of why if we want to show (1) it is equivalent to show (2)? Any idea on why the author does not feel the need to justify this?

  • 1
    $\begingroup$ Your question is impossible to understand, since you are not explaining the following symbols: $F,F',\approx,[p]$. $\endgroup$ Mar 20, 2021 at 0:41
  • 1
    $\begingroup$ Do not revert edits to improve your question. This site is a community resource, which means that others are allowed and encouraged to edit your question to improve it. See cs.stackexchange.com/help/editing. $\endgroup$
    – D.W.
    Mar 20, 2021 at 4:08
  • 1
    $\begingroup$ Do not use images to represent text or mathematics. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics. You can use LaTeX. We require that you give proper attribution to the sources of all copied material. $\endgroup$
    – D.W.
    Mar 20, 2021 at 4:09
  • 2
    $\begingroup$ It doesn't take 100 pages to define the notation that is used in the question. This site is composed of volunteers: if you would like an answer, it is in your interests to make sure the question is understandable and self-contained. $\endgroup$
    – D.W.
    Mar 20, 2021 at 4:11
  • 1
    $\begingroup$ @JMF9, I'm sorry, but as previously explained, that is not a request that can be accommodated on this site. If you would like to explain in what way quality has been reduced I imagine people might be willing to hear. As previously explained, we do not want to see images of text, and I do not see how replacing images with a transcription lowers quality; in my opinion it increases the quality of the question. Please do not continue reverting edits to your question. $\endgroup$
    – D.W.
    Mar 30, 2021 at 7:04

1 Answer 1


Let us start with explaining the notation:

  • $F$ is the set of accepting states of some DFA.
  • We define an equivalence relation $\approx$ on the states of the DFA as follows: $p \approx q$ if for all words $x$, $\hat\delta(p,x) \in F$ iff $\hat\delta(q,x)$, where $\hat\delta$ is the transition function of the DFA (extended from symbols to words).
  • We denote the equivalence class of a state $p$ by $[p]$.
  • $F' = \{ [p] : p \in F \}$.

Now suppose that $[p] \in F'$. According to the definition of $F'$, $[p] = [q]$ for some $q \in F$. Standard properties of equivalence relations imply that $[p] = [q]$ iff $p \approx q$. By definition of $\approx$, $\hat\delta(p,x) \in F$ iff $\hat\delta(q,x) \in F$ for all words $x$. Taking $x = \epsilon$, we see that $p = \hat\delta(p,\epsilon) \in F$ iff $q = \hat\delta(q,\epsilon) \in F$. Since $q \in F$, this shows that indeed $p \in F$.

  • $\begingroup$ It seems like you understood the notation just fine. This answer in no way addresses my question. I understand what the lemma says and what the lemma means. I do not understand how the author determines that showing statement (1) is the same as showing statement (2). Also, the edits you made to my post were unproductive. Again, this response in no way addresses the question. $\endgroup$
    – JMF9
    Mar 20, 2021 at 1:09
  • 3
    $\begingroup$ I didn't "understand the notation just fine". I looked it up in the textbook. There is no reason for me to have to do that. You should provide all necessary information in the post. Granted, you can't tell which information is necessary as a student, but when people tell you to explain your notation, doing it would increase the probability that you will get help. $\endgroup$ Mar 20, 2021 at 1:22
  • $\begingroup$ I'm sorry that you don't like my answer. Perhaps someone else will step in with a better one. $\endgroup$ Mar 20, 2021 at 1:23
  • $\begingroup$ If you want to get help on this site, you have to abide by site rules. $\endgroup$ Mar 20, 2021 at 1:26
  • 1
    $\begingroup$ The site is curated by users. The goal is to create a repository of high quality questions and answers. As part of that, it is better that text in questions be searchable, which means that actual text is preferred over images. That was the main goal of my original edit. $\endgroup$ Mar 20, 2021 at 1:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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