Wednesday, November 26, 2008

Context free grammar

This morning was particularly refreshing. Maybe because I've slept earlier than usual. I was able to get a good grasp of Danny's lecture today.

Our topic today is "Context free grammar". I find this topic interesting in particular because we've been learning about symbols, strings and languages. The topic couldn't have been complete without being able to create proper sentences out of all the languages and symbols that we've defined.

The symbols V,\sigma, P,S all are part of G (grammar). The symbols are broken down as the following:

V - the set of variables
\sigma - the terminals
P - the set of production (rules on how a sentence can be constructed)
S - the starting points

Danny then gave us an example of

G1 : S -> 0S1
S -> \epsilon (empty string)

When I saw this expression, I jumped to the conclusion that the only possible answer was 01. However, analyzing closer at this expression tells us this is not true because S can also be 0S1. Thus, it could mean (0*1*). I feel that though this lesson I have more insight to regular expressions but the way the language of the grammar is still unclear to me.

For example:

L (g) = {alpha | S=>*g x} (Note: * is super script and g is subscript of the implication arrow)

My understanding is that S follows the grammar "g" and can be concatenated * times. Is this what it actually means?

No comments: