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 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 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 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 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 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 at 6:25
  • $\begingroup$ and in your example of automaton, what made it an NFA? $\endgroup$ – Yos Jan 30 at 6:27

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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