91Ó°ÊÓ

Context-free language is generated by context-free grammar. These languages are accepted by Pushdown Automata. These are the supersets 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).$

Here, that the language is a context-free language is proved by some rules, as per which if the grammar follows some properties ofcontext-free language, then it is a context-free language. Also, if the language is capable of passing through pushdown machine, then it will act as a context-free language.

Let’s observe that a string is in $D$if and only if it can be written as

$$\begin{gathered} xywith \\ \left|x\right|=\left|y\right| \end{gathered}$$

Such that for some $i$, the $i$th character of $x$is different from the$i$ th character of y.

To obtain such a string, we start generating the corresponding$i$ th characters, and fill up the remaining characters. Based on the above idea, we define the context-free language for$D$ is as follows:

role="math" localid="1663234599092" $$\begin{gathered} S→AB|BA \\ A→0A0|1A0\left|0A1\right|0 \\ B→0B0\left|0B1\right|1B1|1 \end{gathered}$$

Alternative grammar is

$$\begin{gathered} S→AB|BA \\ A→XAX|0 \\ B→XBX|1 \\ X→0|1 \end{gathered}$$

It follows all the properties of context-freegrammar.

Hence, the language $D$is a context-free language.