1
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Try proving that your construction works. This is how you can verify that it works. $\endgroup$ – Yuval Filmus Jan 29 '19 at 16:16
  • $\begingroup$ 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. $\endgroup$ – Yos Jan 29 '19 at 16:20
2
$\begingroup$

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$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Does $\delta$ function always produce a set when building an NFA? $\endgroup$ – Yos Jan 30 '19 at 5:34
  • 1
    $\begingroup$ Yes, this is the way it is defined. It is a function $Q \times \Sigma \to 2^Q$. $\endgroup$ – Yuval Filmus Jan 30 '19 at 5:47
  • $\begingroup$ and what made my finite automaton an NFA, the fact that I "guess" the end of the word in $L/\{a\}$? $\endgroup$ – Yos Jan 30 '19 at 6:04
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jan 30 '19 at 6:25
  • $\begingroup$ and in your example of automaton, what made it an NFA? $\endgroup$ – Yos Jan 30 '19 at 6:27

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.