Examples Of Context Free Languages (CFL)

So far, we have seen very good examples of Regular expressions and Regular Languages. We will see more difficult problems in future. But at this time, we are going to start examples of context free languages (CFL). There are a lot of problems based on CFL. So we will discuss a lot of problems of CFL.

Example 1
Consider the following input string:
x+2*y

When scanned by a scanner, it produces the following stream of tokens:

id(x)
+
num(2)
*
id(y)

The goal is to parse this expression and construct a data structure (a parse tree) to represent it. One possible syntax for expressions is given by the following grammar G1:

E ::= E + T | E - T | T
T ::= T * F | T / F | F
F ::= num | id

where E, T and F stand for expression, term, and factor respectively. For example, the rule for E indicates that an expression E can take one of the following 3 forms: an expression followed by the token + followed by a term, or an expression followed by the token - followed by a term, or simply a term. The first rule for E is actually a shorthand of 3 productions:

E ::= E + T
E ::= E - T
E ::= T
G1 is an example of a context-free grammar (defined below); the symbols E, T and F are nonterminals and should be defined using production rules, while +, -, *, /, num, and id are terminals (i.e., tokens) produced by the scanner. The nonterminal E is the start symbol of the grammar.

In my next Posts, I will explain types of parsing because knowledge of them is necessary for writing context free grammars.

Context-Free Grammar (formal definition)

Definition of Context-Free Grammar includes the definition of Context free language. So please read the following definition carefully.

Just as any formal grammar, a context-free grammar G can be defined as a 4-tuple:
G = (Vt,Vn,P,S) where
 Vt is a finite set of terminals
 Vn is a finite set of non-terminals
 P is a finite set of production rules
 S is an element of Vn, the distinguished starting non-terminal.
 elements of P are of the form

Vn(Vt U Vn)*

Automata Step by Step

Now we will discuss regular languages in this post.

Regular language:
A regular language is the set of strings generated by a regular grammar. Regular grammars are also known as Type-3 grammars in the Chomsky hierarchy.
A regular grammar can be represented by a deterministic or non-deterministic finite automaton. Such automata can serve to either generate or accept sentences in a particular regular language. Note that since the set of regular languages is a subset of context-free languages, any deterministic or non-deterministic finite automaton can be simulated by a pushdown automaton.
Now you will be curious to know about the terms “deterministic finite automaton”, “non-deterministic finite automaton”, “pushdown automaton” and “context-free languages”.
In next Post, we will discuss only “deterministic finite automaton” and “nondeterministic finite state machine”.