Creating DFA to prove closure properties

Question

I am given a language $L \subseteq \Sigma^*$ and symbol $a \in \Sigma$. Let $a/L= \{ w \in \Sigma^*~|~ wa \in L \}$ ex. String that end in $a$ but with that last $a$ removed. I am trying to prove that for any $L$ and $a$, if $L$ is regular then $a/L$ is also regular by giving a DFA

So what I have tried is creating a DFA for $L$ (if $L$ is regular there exists a DFA for it) and $M = (Q,\Sigma,\delta,q_0,F)$. To show $a/L$ is regular I create a DFA $M' = (Q',\Sigma',\delta',q_0',F')$ and $Q' = Q$, $\delta' = \delta$, $q_0' = \delta(a, q_0)$, $F' = F$. And the starting state for $M'$ is the state of $M$ after receiving a as its last input.

I am not sure if this is the right approach? Did I construct my $M'$ DFA correctly?

Answer 1

I'm not sure about your notations, but it seems you changed the initial state of the automata, while the only thing you have to change is the set of final states of $M$ : the final states of $M'$ will be the subset of $Q$ defined by

• $x\in F' \Leftrightarrow \exists y\in F,~\exists \ell:x \xrightarrow{a} y$, in other words, a state $x$ is a final state in $M'$ if and only iff there is a transition labelled by $a$ from $x$ to a final state of $M$.

Answer 2

It seems your doing the things backwards. If I've correctly understood your definition $a/L$ is the language whose strings are all the strings $w \in \Sigma^*$ that belong to $L$ once you postfix them with an $a$.

The automata you described accepts all those strings $w \in \Sigma^*$ such that belong to $L$ when you prefix them with an $a$. Indeed it accepts all those $w \in \Sigma^*$ such that $$\delta^*(q_0',w)=\delta^*(\delta(q_0',a),w)=\delta(q_0,aw)$$

Here by $\delta^*$ I mean the function $\delta^* \colon Q \times \Sigma^* \to Q$ defined by the equation $$\delta^*(q,aw)=\delta^*(\delta(q,a),w) \text{ where $q \in Q$, $a \in \Sigma$ and $w \in \Sigma^*$}$$

The correct DFA should be $(Q',\Sigma',\delta',q_0',F')$ where

• $Q'=Q$
• $\Sigma'=\Sigma$
• $\delta'=\delta$
• $q_0'=q_0$
• $F'=\{q \in Q \mid \delta(q,a) \in F\}$.

This DFA accepts all those strings $w \in \Sigma^*$ such that $\delta^*(q_0,w) \in F'$ that, by definition $F'$, are exactly all those strings such that $$\delta(\delta^*(q_0,w),a)=\delta^*(q_0,wa) \in F$$ (the fact that $\delta(\delta^*(q,w),a)=\delta(q,wa)$ is a theorem).

Hope this helps.