Concatenation. Suppose L1 and L2 are two languages. Then the concatenation among them can be shown as L1L2. And they should be context-free.

Example:

L1 and L2, L = L1L2 = { anbncmdm }.

CFG- Context-free grammar is closure under. 1) Union 2) Concatenation 3) Kleene Star Operation.

Union: Let suppose L1 and L2 are languages, they must have the finite set of alphabet. And their grammar has to be drawn.

L1  L2 has to be context-free.

Example: 

S → aS

S → φ

S → bS

S → φ

S → aS|bS|φ

Kleene Star: Suppose L is a context-free language, then L* is also context-free language.

Example:

L1 = { anb}*

Intersection− If L1 and L2 are two context-free languages, then L1 ∩ L2 is may or may not necessarily context-free.

Intersection with Regular Language− If L1 is a regular language and L2 is a context-free language.

Regular language

Definition of Regular Language A Regular language whose regular expressions can be drawn is known as regular language. Property of Regular Language: Closure Property: If L and M are two…

Continue Reading Regular language