Wednesday, December 3, 2008

Context free grammar

Context-free grammar (CFG) describes how sentances in a language are built recursively using a set of rules, the operations given as variables on the left hand side of the equation and the nouns, verbs, etc given as terminals on the right. After doing the exercises in class, I found I had little trouble with the concept. I think I found the concept to be very natural and intuitive after doing DFSA, as the motivations behind the rules seem similar. I decided to look up more about the limitations and extensions around CFGs. An interesting example of an undecidable language, one for which a CFG does not exist, I stumped onto was the case of language that accepts every string. Extending this, it seems that it is in many ways undecidable if two CFGs, that are not precisely equal, describe the same language. I also found it interesting how people had extended the power of CFGs by allowing the nonterminal elements to have arguements, which allows for natural language features such as references and agreement. I'm interested also in seeing how context sensitive grammar works as well as how CFGs are used in computers.

No comments: