Context Free Language

The main difference between CFL and a Regular language is that of the production rule. In RL the production rule is not an iteration, that is, it cannot contain an empty symbol.

However in a CFL the production rule is a closure, that is it can contain an empty symbol.

Example

https://www.youtube.com/watch?v=htoFbcwES28&list=PLBlnK6fEyqRgp46KUv4ZY69yXmpwKOIev&index=72

Derivation Tree

https://www.youtube.com/watch?v=u4-rpIlV9NI&list=PLBlnK6fEyqRgp46KUv4ZY69yXmpwKOIev&index=73

Ambiguous Grammar

Here instead of drawing a tree, the variables were used on the left and right side respectively.

Simplification of CFG : Basics

https://www.youtube.com/watch?v=EF09zxzpVbk&list=PLBlnK6fEyqRgp46KUv4ZY69yXmpwKOIev&index=75

Example

Phase 1

STEP 1: Make a set of all the terminal symbols (small letters)

$T = {a, c, e}$

And a set of the non-terminal symbols $W_{1}$

$W_{1} = {A, C, E}$

Now make another set $W_{2}$ which contains all the symbols of $W_{1}$ and the symbols which can derive these symbols.

We add the symbol S in $W_{2}$ since S can derive the symbols A and C

Therefore, $W_{2} = {A, C, E, S}$

Continue this if anymore symbols can be added, or else stop.

Phase 2

Make a new Grammar G’ which is an equivalent of grammar G, such that :

$G^{'} = {(V), (T), P, (S)}$

where V = variables/non-terminal symbols, T = terminal symbols, P = production rules and S = Start symbol

Thus the new production rule P will be : S → AC, A→a, C→c, E→aA | e .

We ignored B in this rule since B was not included in any of the sets.

Now make a new set $Y_{1}$ which contain the start symbol S

Therefore, $Y_{1} = {S}$

And make another set $Y_{2}$ which will contain S and all the symbols derivable from S.

$Y_{2} = {S, A, C}$

Now make another set $Y_{3}$ which will contain all the current symbol as well as all the terminal symbols derivable from $Y_{2}$ .

Thus, $Y_{3} = {S, A, C, a, c}$

Notice how E and it’s derivations got skipped as well. Since E was redundant.

Thus the new reduced grammar.

Simplification of CFG : Removal of Unit productions

https://www.youtube.com/watch?v=B2o75KpzfU4&list=PLBlnK6fEyqRgp46KUv4ZY69yXmpwKOIev&index=76

Example

Here we need to find the type of productions which are of the type A→B and B→any sort of terminal symbols.

Basically following a whole transitive approach.

So, we can find in the example that :

M → N and N → a.

So we can simply substitute M→a instead.

P becomes : S→XY, X→a, Y→Z|b, Z→M, M→a

Again the same applies for Z→M, M→a

We can substitute Z→a instead.

Therefore, P : S→XY, X→a, Y→Z|b, Z→a

Now again the same applies to Y→Z and Z→a.

We can substitute Y→a instead.

Therefore, P : S→XY, X→a, Y→a|b

It may seem that S→X|Y and the same applies here too since X→a, Y→a|b, but we don't modify the start symbol.

Therefore the reduced grammar will be :

P : S→XY, X→a, Y→a|b.

Simplification of CFG (removal of NULL productions)

https://www.youtube.com/watch?v=mlXYQ8ug2v4&list=PLBlnK6fEyqRgp46KUv4ZY69yXmpwKOIev&index=77

STEP 1: Find all productions in the form of $A - >\in$ STEP 2: Replace those productions with just $\in$

So basically we will pair the original productions with the non-terminal variables on the left, followed by the | and the replaced variants of the symbol on the right

Therefore in S, we can get the following production:

S → ABAC S → ABC | BAC | BC

For A→aA | $\in$

we get : A → a

similarly for B → bB | $\in$

B → b

Therefore the new production accordingly will be :

Chomsky Normal Form(CNF) and CFG to GNF conversion

https://www.youtube.com/watch?v=Mh-UQVmAxnw&list=PLBlnK6fEyqRgp46KUv4ZY69yXmpwKOIev&index=78

In Chomsky Normal Form, we have a restriction on the length of RHS, which is, elements in RHS should either be two variables or a Terminal variable.

where A, B, C are non-terminals and a is a terminal variable.

Conversion of CFG to CNF

https://www.youtube.com/watch?v=FNPSlnj3Vt0&list=PLBlnK6fEyqRgp46KUv4ZY69yXmpwKOIev&index=79 [Recommended to watch]

Example

Step 1: Check if there is a start symbol on the right hand side of the production Step 2: If so, then create a production $S^{'} - > S$ :

Step 3: Remove NULL productions

Here we first remove $B - >\in$ , followed by $A - >\in$

Step 4: Remove all Unit Productions

Here in STEP 4: We found the productions that has more than two variables in RHS.

Thus we have to replace the variables SA with a new one named X.

and in STEP 5: we replaced a with the variable Y.

Both STEP 4 and STEP 5 needed to be enacted since they were violating CNF.

Greibach Normal Form and CFG to GNF conversion

So initially we checked if the given grammar had any unit or null productions [Check Passed] Next we checked whether the CFG is already in CNF or not. [Check Passed] So then we simply rename the variables into a form of $A_{i}$ with the value of i starting from 1.

Now we need to alter the rules such that there are no non-terminal symbols $A_{i}$ > $A_{j}$ or $A_{i} - > A_{j} x$ , where i < j .