Context-Free Grammar

languages

Definition

Context-Free Grammar (Type-2)

A grammar $G=(N,T,P,S)$ is called context-free (Type-2) if every production in $P$ is of the form

$$A\to \beta$$

where $A\in N$ and $\beta \in (N\cup T{)}^{\ast }$.
That is, the left-hand side of every production consists of a single nonterminal.

A language is called context-free there exists a pushdown automaton that accepts it.

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.

Parallel Derivation

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