CFG Properties and Applications

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 have to be drawn.

L1 ∪ L2 has to be context-free.

Example: 

S → aS

S → φ

S → bS

S → φ

S → aS|bS|φ

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:

L₁ and L₂, L = L₁L₂ = { aⁿbⁿc^md^m }.

Kleene Star:

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

Example:

L₁ = { aⁿbⁿ }*

• 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, then L1 ∩ L2 is a context-free language.
• Complement− If L1 is a context-free language, then L1’ may not be context-free.

Applications of Theory of Automata:

The applications of the Theory of Automata are as follows:

1. Compiler Construction
2. Programming Languages
3. Linder-Mayer System
4. Natural Language Processing

Ambiguity in Context-Free Grammar