Posts

Showing posts from December 12, 2010

Context Free Grammar

Image
Context Free Grammar (CFG)

A Context Free Grammar is a "Machine" that creates a Language.A Language created by a Context Free Grammar is called a Context Free Language (CFL).The Class of Context Free Languages properly contains the class of Regular Language.


Applications of CFG.

CFG are extensively used to specify the syntax of programming Languages, and now the structure of document like XML's Document Type DefinitionCFG used to develop Parser. (Specification and Compilation of Programming Language)Meaning of Context Free?
If at some point in a derivation we have obtained a string α containing the variable A, then we may continue by substituting β  for A, No matter what the string α1  and α2 are. That is independent of the Context.