If A and B are languages define A circle Bxyx elementof A an

If A and B are languages, define A circle B={xy|x elementof A and y elementof B and |x|=|y|}. Prove that if A and B are regular languages, then A circle B is context free.

Solution

If A and B are regular, they can be represented by a NFA. Suppose A and B are both languages that accept the string of same length.by drawing the NFA\'s and we can say the contatenation can easily be performed.this proves that AB is a regular languageSince it can be represented as an NFA. Because a PDA is essentially an NFA with a stack, AB can be represented by using a PDA with the stack omitted. Thus AB is a context free language.