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 )


"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.

  • $\begingroup$ Intersection of languages is just like intersection of sets. $\endgroup$ – Yuval Filmus Sep 6 '18 at 4:56
  • $\begingroup$ Your question is a bit hard to understand. $\endgroup$ – Yuval Filmus Sep 6 '18 at 4:56
  • $\begingroup$ @Yuval Filmus Which part is unclear ? $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ Yuval Filmus : Can u frame a simple CFG for concatenation and intersection of two languages. $\endgroup$ – CHETAN RAJPUT Sep 6 '18 at 5:20
  • $\begingroup$ I suggest consulting a textbook on automata and formal languages. $\endgroup$ – Yuval Filmus Sep 6 '18 at 5:37
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Sep 6 '18 at 5:41
  • $\begingroup$ It will be fine if u can frame a regular for complement and intersection as cfg not closed under intersection $\endgroup$ – CHETAN RAJPUT Sep 6 '18 at 17:19
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Sep 6 '18 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.