Context-Free Grammars « Paul Nicholls

25May/090

Context-Free Grammars

Context-Free Languages (CFLs) are more powerful than Regular Languages (provably so) and can be defined by means of Context-Free Grammars or Push-Down Automata. Any context free language can be represented with either of these methods. CFLs closely relate to both human languages and programming languages and their applications tend to fall within these fields.

A Context-Free Grammar (CFG) is essentially a collection of substitution rules of the form $A \rightarrow b$ where $A$ is a variable (or nonterminal symbol) and $b$ is a string of terminal and nonterminal symbols.

The formal definition of a Context-Free Grammar is a four tuple $\left( V, \Sigma, R, S \right)$ where:

$V$ is a finite set of non-terminals
$\Sigma$ is a finite set of terminals such that $V \cap \Sigma = \phi$
$R$ is a finite set of production rules which take the form $T \rightarrow w$ where $T \in V , w \in \left( V \cup \Sigma \right)*$
$S$ is the start variable and $S \in V$

For example, we can denote $uTv \Rightarrow uwv$ if $T \rightarrow w$ and so on.

Grammars can be established to model a range of applications from mathematical equations to human language constructs.

Chomsky Normal Form

Chomsky Normal Form is a theorum that every CFG can be written in the form:

$A \rightarrow BC \\A \rightarrow a \\S \rightarrow \varepsilon$

Where $A \neq S, B \neq S$

Many proofs in the field of context-free languages make use of this form since due to its expanisve nature the derivation of a string on length $n$ always predictably involves $2n - 1$ steps, and a parse tree generated from a Chomsky Normal Form grammar will always be a binary tree of height at most $n$ .

Tagged as: TC, TC-MC Leave a comment

Comments (0) Trackbacks (0) ( subscribe to comments on this post )

No comments yet.

Tweets

@Ed_BigMac because intended audience is 12-17 y/o girls and petite homosexuals? 2012/05/17
RT @georgedthompson: That moment when get all the way back to your room and your key card doesn't work :( 2012/05/15
somehow two trucks has turned into 5; but hey ho off to Bournemouth we go.... (thanks @wickedtechnical !) 2012/05/11
work - McDonald's - sleep - work is becoming a worrying pattern this week #fb 2012/05/09

Lifestream

Checked in at Marriott Hotel

— 7h ago via Foursquare
Listened to 25 songs.

— 21h ago via Last.fm
Checked in at Marriott Hotel

— 1d ago via Foursquare
Checked in at Marriott Hotel

— 2d ago via Foursquare
Checked in at Sandbach Motorway Service Area (South)

— May 17th via Foursquare
Checked in at Prospect Place

— May 16th via Foursquare
Checked in at Warwick Northbound Motorway Services

— May 16th via Foursquare
Checked in at Holiday Inn Winchester

— May 15th via Foursquare

Paul Nicholls Stuff