# Context Free Languages

A context free language (CFL) is a language generated by a context free grammar (CFG). A CFG is a set of rules for deriving (or generating) strings (or sentences) in a language.

Informally, a CFG consists of:â€“

â€” A set of replacement rules, each having a LHS and a RHS.

â€” Two types of symbols, variables and terminals.

â€” LHS of each rule is a single variable (no terminals).

â€” RHS of each rule is string of zero or more variables and terminals.

â€” A string consists of only terminals.

Formally, a CFG is a 4-tuple (V, Î£, R, S), where

- V is a finite set called variables.
- Î£ is a finite set, disjoint from V, called terminals.
- R is a finite set of rules, with each rule being a variable and a string of variables and terminals.
- S âˆˆ V is the start variable.

**Chomsky Normal Form**

A context free grammar is in Chomsksy Normal Form if every rule is of the form.

A â†’ BC

A â†’ a

where, a is any terminal and A, B and C are any variables except B and C may not be the start variable. In addition, the rule S â†’ Îµ, where S is the start material is allowed.

Backus Naur Form

An example of a context-free grammar in BNF is given

# Push Down Automata

Push Down Automata are like non-deterministic finite automata but have an extra component called a stack. The stack provides additional memory beyond the finite automata provides.

Formally, a push down automata is a 6-tuple (Q, Î£, Î“, Î´, q_{0}, F), where

- Q is the set of states.
- Î£ is the input alphabet.
- Î“ is the stack alphabet.
- Î´ : Q Ã— Î£
_{Îµ}Ã— Î“_{Îµ}â†’ P (Q Ã— Î“_{Îµ}) is the transition function. - q
_{0}âˆˆ Q is the start state, and - F âŠ† Q is the set of accept states.

Below is the description of PDA that recognizes the language {0^{n} 1^{n}|n â‰¥ 0}. Let M_{1} be (Q, Î£, Î“, Î´, q_{1}, F), where

Q = {q_{1}, q_{2}, q_{3}, q_{4}}

Î£ = {0, 1}

Î“ = {0, $} $ = This signifies that stack is empty

F = {q_{1}, q_{4}} and

Î´ is given by the following table, where in blank entries signify Ï†.

We can also use a state diagram to describe a PDA, as shown below:â€“

- A language is context free if and only if some push down automata recognizes it.
- Every regular language is context free language.

**Pumping Lemma for CFL**

If A is a CFL, then there is a number P (the pumping length) where, if S is any string in A of length at least P, then S may be divided into five pieces S = uvwxy satisfying the conditions:â€“

- for each i â‰¥ 0, uv
^{2}wx^{2}y âˆˆ A, - |vx| > 0, and
- |vwx| â‰¤ P.