Module 2.5: Context Free Languages

Formal Languages

Classified in to different language classes based on the computational power required to recognize them.

Chomsky Hierarchy

The classification of formal languages forms the basis for the _________, which divides languages into four types, each corresponding to a different class of automata.

Type 0-Recursively Enumerable
Type 1-Context Sensitive
Type 2-Context Free
Type 3-Regular

Classes of Formal Languages

Type 3-Regular Languages

The simplest type of formal languages and can be recognized by finite state machines. These languages have a structure that can be described using regular expressions or regular grammars.

Finite Automata (FA)

Automaton of Regular Languages.

Production Rule Form

The regular language is _______, where in the non terminal symbol or variable is places at the rightmost (leftmost) part of the string.

Type 2-Context Free Languages

More expressive than regular languages and can be recognized by push down automata.

Context Free

All regular languages are considered as ________ since it is a subset but not the other way around.

Context-Free Grammars (CFG)

Allow rules where a single non-terminal symbol is replaced by a string of terminals and/or non-terminals.

Pushdown Automata (PDA)

Automation of Context-Free Language.

Generated by Context Free Grammars
Recognized by Push Down Accepters

Context Free Languages can be

Modeling Languages

Context-free languages are particularly suited for ________ with nested or recursive structures.

Growing only one side of the string.
Only one terminal symbol per production rule.

Restrictions of CFG

V
T
P
S

Grammar definition, a 4 tuple G

V

Finite set of non terminal symbols or variables.

T

Finite set of terminal symbols.

P

Finite set of production rule.

S

Start symbol.

Parse Tree

Illustrate the derivation process of a string. When a string is derived using leftmost or rightmost direction, the parse tree will be the same.

Leftmost Derivation
Rightmost Derivation

Derivations in CFG will now vary. Since multiple non terminal symbols can appear multiple times in a production rule, replacement can be done in one of the two directions.