Context Free Grammars and Languages

In formal language theory, a Context Free Language is a language generated by some Context Free Grammar.

The set of all CFL is indentical to the set of language accepted by Pushdown Automata(PDAs)

---

Context Free Language

Context Free Grammar is defined by 4 tuples as:

$$G=\{V,\Sigma ,S,P\}$$

Where:

• $V$ - set of Variables or non-terminal symbols
• $\Sigma$ - set of terminal symbols
• $S$ - start symbol
• $P$ - production rule

Important

Context Free Grammar has Production Rule of the form

$$A\to a$$

where, $a=\{V\cup \Sigma {\}}^{\ast }$ and $A\in V$

Example

Example

For generating a language that generates equal number of $a$‘s and $b$‘s in the form $a^n{b}^n$, the Context Free Grammar will be defined as:

$$G=\{(S,A),(a,b),(S\to aAb,A\to aAb\mid \in )\}$$