Context-Free Language

languages

Definition

Context-Free Language

A context-free grammar is described by a tuple

$$⟨V,T,P,S⟩$$

where

• $V$ is the set of non-terminal symbol
• $T$ is the set of terminal symbols with $V\cap T=\varnothing$
• $P\subseteq V\times (V\cup T{)}^{\ast }$ is the set of production rules
• $S\in V$ is the start non-terminal symbols

From the start symbol, non-terminal symbols are iteratively replaced by applying the respective production rules.

Derivation

Leftmost Derivation

Leftmost derivation is process of iteratively replacing the leftmost non-terminal symbol by applying the respective production rules.

Rightmost Derivation

Rightmost derivation is process of iteratively replacing the rightmost non-terminal symbol by applying the respective production rules.

Paralell Derivation

Paralell derivation is process of iteratively replacing the all non-terminal symbols by applying the respective production rules.