FORMAL LANGUAGES and AUTOMATA THEORY

Context-Free Grammer

 

Definition:

Context-Free Grammar (CFG) is a set of production rules that describe all possible strings in a given formal language. For example;

 

A →  x

A → y

B →  z

 

With these defined rules, we can replace A with 'x' or 'y' ; with 'z' for output. Context-Free Grammar G is defined by the 4 value;

 

G=( V , T , P , S )

 

= In grammer rules, this shows the elements named "variables" where be on the left side of grammer arrows. Variables are not include in our outputs. For our example  V={A,B}. 

= In grammer rules, this shows the elements named "alphabet" where be on the right side of grammer arrows. We create the output with these elements. For our example T={x,y,z}. 

= This symbolize set of Grammer rules.

= This indicate the Start State. Start state shows us to which rule or rules we have to use to apply the grammer rules. For our example S={A}.

Let's use these with example

Example 1:

 S → 0A01 
 A → 1B 
 B → 010

Let's start with determination of these gammer G's values;

V = {A , B}       T = {, 0}        = {S}   ===>  G=({A , B} , {0} , , {S})

 Now we can generate out output. For example we can generate this output with given grammer rules;

S → 0A01  01B01  0101001

For understand better, we can represent example with Derivation Tree.

tree

Practical Example 1:

 E →  E +
 E → E * E 
 E → number

This example's grammer rules make addition and multiplication. Let's assume the = 2*3+4 and when we apply the grammer rules to E, it will be accepted.

Let's try to draw this example's derivation tree:

Tree                      Tree

As you can see, with this grammer rules, we can draw more than one derivation trees. This situation called a Ambigous. We need to add some variables to solve this problem. When we add some variables to grammer rules, this derivation trees can not be same.

 E →  T | E +
 E →  | * F 
 F → number

Now we can draw a derivation tree of this rules.

tree 

Practical Example 2:

 E →  T | E - 
 E →  | T / F 
 F → number | ( E )

In this example, you can try the grammer rules via program. With given Expression, you can examine how grammer rules work.

 

Program: Context-Free Grammer Exampler

References:

1) https://www.wikiwand.com/en/Context-free_grammar

2) Above examples what we work on, derived from examples in Automata Theory lesson's laboratory studies.

 

Created by Ahmet Fırat ŞÜPHESİZ