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?

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

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$
10
  • $\begingroup$ Does $\delta$ function always produce a set when building an NFA? $\endgroup$
    – Yos
    Jan 30, 2019 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, 2019 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, 2019 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, 2019 at 6:25
  • $\begingroup$ and in your example of automaton, what made it an NFA? $\endgroup$
    – Yos
    Jan 30, 2019 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.