# Difference between concatenation of two languages and Intersection of two languages

Please also explain in terms of closure of these languages and plot a difference using specific example.

I am interpreted like this and now i am confused.

S1 and S2 are two languages.

"S --> S1. S2 " ( S1 followed by S2 hence concatenation )

and

"S--> S1.S2" ( S1 'and' S2 hence Intersection)

Correct me where I am going wrong.

P.S :

Also explain , In case of CFL's - Language is closed under Concatenation but not Intersection.

• Intersection of languages is just like intersection of sets. – Yuval Filmus Sep 6 '18 at 4:56
• Your question is a bit hard to understand. – Yuval Filmus Sep 6 '18 at 4:56
• @Yuval Filmus Which part is unclear ? – CHETAN RAJPUT Sep 6 '18 at 5:01

The concatenation of two languages $L_1,L_2$ is defined as follows: $$L_1L_2 = \{w_1w_2 : w_1 \in L_1, w_2 \in L_2\}.$$ In words, we take all words in $L_1$ and concatenate to them all words in $L_2$.

The intersection of two languages $L_1,L_2$ is the set of words they have in common.

As an example, \begin{align*} &\{a\} \{b\} = \{ab\}, && \{a\} \cap \{b\} = \emptyset, \\ &\{a\} \{a\} = \{aa\}, && \{a\} \cap \{a\} = \{a\}, \\ &\{a\} \{a,b\} = \{aa,ab\}, && \{a\} \cap \{a,b\} = \{a\}. \end{align*}

The concatenation and intersection of two regular languages is regular. In contrast, while the concatenation of two context-free languages is always context-free, their intersection is not always context-free. The standard example is $\{a^nb^nc^m : n,m \geq 0\} \cap \{a^nb^mc^m : n,m \geq 0\} = \{a^nb^nc^n : n \geq 0\}$. However, the intersection of a context-free language with a regular language is always context-free.

• Yuval Filmus : Can u frame a simple CFG for concatenation and intersection of two languages. – CHETAN RAJPUT Sep 6 '18 at 5:20
• I suggest consulting a textbook on automata and formal languages. – Yuval Filmus Sep 6 '18 at 5:37
• Given context-free grammars for $L_1,L_2$ with starting symbols $S_1,S_2$, you can create a context-free grammar for $L_1L_2$ by adding a new starting symbol $S$ and a production $S \to S_1S_2$. A similar construction works for union, using the productions $S \to S_1|S_2$. Since the context-free languages are not closed under intersection, no such construction is possible for intersection. – Yuval Filmus Sep 6 '18 at 5:41
• It will be fine if u can frame a regular for complement and intersection as cfg not closed under intersection – CHETAN RAJPUT Sep 6 '18 at 17:19
• You are basically asking me to reproduce a textbook on context-free languages. Many such textbooks and lecture notes exist, and should contain all the information you seek. – Yuval Filmus Sep 6 '18 at 17:21