Let $A/B = \left\{w\mid wx \in A\text{ for some }x\in B\right\}$.
Show that if $A$ is regular and $B$ is any language, then $A/B $ is regular.
My understanding is that we know only about $A$ which is regular but $B$ can be any language (may be non regular). $w$ string is our input. We are checking for existence of a string $x\in B$ such that $wx\in A$.
As I know two non-regular languages can also be concatenated to produce a regular language, so how is this question valid?
Is it like this? As $x$ is just a string which will be finite, so its regular (confused here also). Even if $x$ is regular, because the concatenation of a non regular and regular can also give regular language. So how can we say $w$ will also be regular?
Please clarify.
Best Answer
HINT: Start with a DFA $M=\langle Q,\Sigma,\delta,q_0,F\rangle$ for $A$, where the alphabet $\Sigma$ is the union of the alphabets for $A$ and $B$. Let $\bar\delta:Q\times\Sigma^*\to Q$ be the extended transition function: $\bar\delta(q,w)=q'$ if $M$ goes to state $q'$ when it starts in state $q$ and reads the word $w$.
To get a DFA for $A/B$ you need only modify $F$, the set of acceptor (final) states. Change it to
$$F'=\left\{q\in Q:\exists x\in B\,\left(\bar\delta(q,x)\in F\right)\right\}$$
I’ll leave it to you to show that this works.