Question

Let

$A/B=\left\{w\right|wx\in aAforsomex\in B\}$Show that if$A$is context free and$B$is regular, then$A/B$is context free

Short answer

Yes, if $A$is context free and $B$is regular, then$A/B$is context free is proved.

Step-by-step solution

Define context free and regular language

The context free language is generated by context free grammar.

These languages are accepted by Pushdown Automata. These are the superset of regular languages.

Consider context-free languages $L_1$described as$G_1=(V_1,S,R_1,S_1).$

Consider context-free language $L_2$described as $G_2=(V_2,S,R_2,S_2).$

A language is regular if it can be expressed in terms of regular expression.A regular expression can also be described as a sequence of pattern that defines a string. Regular expressions are used to match character combinations in strings.

Explanation

Yes, if $A$is context free and $B$is regular, then $A/B$is context freez.

Let $M=\left(Q,\Sigma ,\delta ,q_0,F\right)$be a deterministic finite automata for $A$.

And consider $M$be a deterministic finite automata for $B$and $M$ ^I be a pushdown deterministic automata for $A$. As given in the question $A$is context free and $B$is regular, then $A/B$is context free.

Here construct a pushdown deterministic automata for $A/B$by modifying $M$’ so that it can run simultaneously (using the Cartesian product) $M$’s finite state control in addition to its own finite state control. Initially, only the original logic of $M$’ is run.

The modified machine, using nondeterminism, will start up $M$after it will read. From this point onward, the machine guesses a string $x,$and processes $x,$by both $M$and $M$’.The machine will accept only if both machines simultaneously accept.

Yes. Let $M=\left(Q,\Sigma ,\delta ,q_0,F\right)$be a deterministic finite automata for $A$.

Here a state $q\in Q,$

And define , $Lq=\left\{x\right|\delta \left(q,x\right)\in F\}.$

Then $M_0=\left(Q,\Sigma ,\delta ,q_0,F_0\right)$is a deterministic finite automata for $A/B$where

$F_0=\left\{q\right|L_0\cup B\ne E\}.$

Hence, if$A$ is context free and $B$is regular, then $A/B$is context free is proved.