Question

If $\mathbf{A}$and role="math" localid="1659713811445" $\mathbf{B}$ are languages, define$\mathbf{A}\mathbf{\diamond }\mathbf{B}\mathbf{=}\mathbf{\left\{}\mathbf{xy}\mathbf{\right|}\mathbf{x}\mathbf{\in }\mathbf{Aandy}\mathbf{\in }\mathbf{Band}\mathbf{\left|}\mathbf{x}\mathbf{\right|}\mathbf{=}\mathbf{\left|}\mathbf{y}\mathbf{\right|}\mathbf{\}}$Show that if A and$\mathbf{B}$are regular languages, then$\mathbf{A}\mathbf{\diamond }\mathbf{B}$ is a CFL.

Short answer

$\mathrm{A}\diamond \mathrm{B}=\left\{\mathrm{xy}\right|\mathrm{x}\in \mathrm{Aandy}\in \mathrm{Band}\left|\mathrm{x}\right|=\left|\mathrm{y}\right|\}$

Here, A and $\mathrm{B}$are regular languages so,$\mathrm{A}\diamond \mathrm{B}$ is a context free language is proved.

Step-by-step solution

Define the property of CFG.         

$\mathrm{A}\diamond \mathrm{B}=\left\{\mathrm{xy}\right|\mathrm{x}\in \mathrm{Aandy}\in \mathrm{Band}\left|\mathrm{x}\right|=\left|\mathrm{y}\right|\}$A and$\mathrm{B}$are regular languages so,$\mathrm{A}\diamond \mathrm{B}$ is a context free language. This statement is proved by a finite automaton or adeterministic finite automaton if the given language is valid for the deterministic finite automata then it will also work on the pushdown automata.

For regular grammar containing the regular language a deterministic finite automaton must be applicable for $\mathrm{A}\diamond \mathrm{B}=\left\{\mathrm{xy}\right|\mathrm{x}\in \mathrm{Aandy}\in \mathrm{Band}\left|\mathrm{x}\right|=\left|\mathrm{y}\right|\}$as well as for context free grammar containing language a pushdown automata machine is supported by the given language.

Proving for Language is not CFG.

$\mathrm{A}\diamond \mathrm{B}=\left\{\mathrm{xy}\right|\mathrm{x}\in \mathrm{Aandy}\in \mathrm{Band}\left|\mathrm{x}\right|=\left|\mathrm{y}\right|\}$

Consider machine one and machine two be DFAs deterministic finite automata for $\mathrm{A}$and$\mathrm{B}$respectively.

Now construct PDA push down automata machine one and machine two for $\mathrm{A}\diamond \mathrm{B}$using. On input string. Then start running it on machine one and go on pushing symbols on stack.

When there is machine one is in final state at some point of time, guess non-deterministically that machine have seen first half that is x.

And now $\mathrm{B}$have to run remaining. So now start running it on$\mathrm{B}$and go on poping symbols from stack.

If input is done and stack is empty at same time and also machine two is in final state then accept, else reject.

The given language isare regular languages so, $\mathrm{A}\diamond \mathrm{B}$is a context free language.

This statement is proved by a finite automaton or adeterministic finite automaton if the given language is valid for the deterministic finite automata then it will also work on the pushdown automata.

For regular grammar containing the regular language a deterministic finite automaton must be applicable for $\mathrm{A}\diamond \mathrm{B}=\left\{\mathrm{xy}\right|\mathrm{x}\in \mathrm{Aandy}\in \mathrm{Band}\left|\mathrm{x}\right|=\left|\mathrm{y}\right|\}$.as well as for context free grammar containing language a pushdown automata machine is supported by the given language.

So, the given language is $\mathrm{A}\diamond \mathrm{B}=\left\{\mathrm{xy}\right|\mathrm{x}\in \mathrm{Aandy}\in \mathrm{Band}\left|\mathrm{x}\right|=\left|\mathrm{y}\right|\}$context free language. Here it is proved that A and $\mathrm{B}$are regular languages so, $\mathrm{A}\diamond \mathrm{B}$is a context free language.