# Context Free Gramma

Just a reference from here http://en.wikipedia.org/wiki/Context-free_grammar

A context-free grammar *G* is defined by the 4-tuple

where

- is a finite set; each element is called
*a non-terminal character*or a*variable*. Each variable represents a different type of phrase or clause in the sentence. Variables are also sometimes called syntactic categories. Each variable defines a sub-language of the language defined by . - is a finite set of
*terminal*s, disjoint from , which make up the actual content of the sentence. The set of terminals is the alphabet of the language defined by the grammar . - is a finite relation from to , where the asterisk represents the Kleene star operation. The members of are called the
*(rewrite) rule*s or*production*s of the grammar. (also commonly symbolized by a ) - is the start variable (or start symbol), used to represent the whole sentence (or program). It must be an element of .

### Production rule notation

A production rulein is formalized mathematically as a pair , where is a non-terminal and is a string of variables and/or terminals; rather than using ordered pair notation, production rules are usually written using an arrow operator with as its left hand side and as its right hand side: .

It is allowed for to be the empty string, and in this case it is customary to denote it by ε. The form is called an ε-production.^{[4]}

It is common to list all right-hand sides for the same left-hand side on the same line, using | (the pipe symbol) to separate them. Rules and can hence be written as .

### Rule application

For any strings , we say directly yields , written as , if with and such that and . Thus, is the result of applying the rule to .

### Repetitive rule application

For any we say yields written as (or in some textbooks), if such that

### Context-free language

The language of a grammar is the set

A language is said to be a context-free language (CFL), if there exists a CFG , such that .

### Proper CFGs

A context-free grammar is said to be *proper*, if it has

- no
*inaccessible*symbols: - no
*unproductive*symbols: - no ε-productions: ε

(the right-arrow in this case denotes logical “implies” and not grammatical “yields”) - no cycles:

### Example

The grammar , with productions

- S → aSa,
- S → bSb,
- S → ε,

is context-free. It is not proper since it includes an ε-production. A typical derivation in this grammar is

- S → aSa → aaSaa → aabSbaa → aabbaa.

This makes it clear that . The language is context-free, however it can be proved that it is not regular.