# How to build a finite automaton for right quotient of a regular language?

Let $$L$$ be a regular language over $$\Sigma=\{a,b,c\}$$. Build a finite automaton for $$L/\{a\}$$.

Because $$L$$ is regular then a DFA exists for it: $$A=(\Sigma, Q, q_0, F, \delta)$$.

Let $$M$$ be a finite automaton, $$L(M)=L/\{a\}$$.

$$M=(\Sigma, Q\times\{0,1\}, (q_0,0), \delta', F\times\{1\})$$ with the transition function defined below for all $$q\in Q, \sigma \in \Sigma$$: $$\delta'((q,0),\sigma)=(\delta(q,\sigma),0)\\ \delta'((q,0),\epsilon)=(\delta(q,a),1)$$

The reasoning is that in state $$0$$ we just read letters in $$M$$ because those exact letters also exist in $$L$$. But when we reach end of input in $$M$$ via $$\epsilon$$ we still need to read $$a$$ in $$L$$. I'm not sure if it's valid to assume that $$\epsilon$$ means end of input?

• Try proving that your construction works. This is how you can verify that it works. – Yuval Filmus Jan 29 at 16:16
• To me it seems correct, for example if $aba\in L\implies ab \in L/\{a\}$. Using the derivation rules in the automaton $a$ and $b$ are read in $0$ state. Then the word ends and final $a$ is read in $L$ and the state is changed to $1$ which means we're in accepting state. – Yos Jan 29 at 16:20

First of all, note that you are constructing an NFA, and so $$\delta'$$ should output a set of possible transitions.
You can prove by induction the following identities: \begin{align*} \delta'((q,0),w) &= \{ (\delta(q,w),0), (\delta(q,wa),1)\}, \\ \delta'((q,1),w) &= \begin{cases} \{(q,1)\} & w = \epsilon, \\ \emptyset & w \neq \epsilon. \end{cases} \end{align*} In particular, $$\delta'((q_0,0),w)$$ intersects $$F \times \{1\}$$ iff $$\delta(q_0,wa) \in F$$. In other words, $$w$$ is accepted by your NFA iff $$wa \in L$$, so your automaton is computing $$L/a$$.
You can simplify your construction by taking the original DFA and simply modifying the set of accepting states, replacing $$F$$ with $$F' = \{ q : \delta(q,a) \in F \}.$$ The new automaton accepts a word $$w$$ iff $$\delta(q_0,w) \in F'$$ iff $$\delta(q_0,wa) = \delta(\delta(q_0,w),a) \in F$$ iff $$wa \in L$$.
• Does $\delta$ function always produce a set when building an NFA? – Yos Jan 30 at 5:34
• Yes, this is the way it is defined. It is a function $Q \times \Sigma \to 2^Q$. – Yuval Filmus Jan 30 at 5:47
• and what made my finite automaton an NFA, the fact that I "guess" the end of the word in $L/\{a\}$? – Yos Jan 30 at 6:04
• An $\epsilon$-NFA actually has a transition function of type $Q \times (\Sigma \cup \{\epsilon\}) \to 2^Q$. Your automaton has $\epsilon$-transitions, so in particular it must be an ($\epsilon$-)NFA. – Yuval Filmus Jan 30 at 6:25