FOR FREE CONTENT

Constructing CFG from CFL:

Prerequisite: Chapter (Grammar construction from language) and Chapter (Identification of language)

We already discuss the construction of grammar from the language at chapter (Grammar construction from language)

Still we discuss some of the CFG construction from CFL:

1.  Grammar of palindrome language:

We already discussed the grammar of the above palindromes.

2.  Write the grammar of the language

Solution:

This given language is a Deterministic Context Free Language (DCFL).

Corresponding grammar:

3. Construct the grammar of the given language

Solution:

This given language is a DCFL.

Corresponding grammar:

4. Write the grammar of the language

Solution:

This given language is a DCFL.

Corresponding grammar:

5. Write the grammar of the language

Solution:

This given language is a DCFL.

Corresponding grammar:

6. Write the grammar of the language

Solution:

This given language L = set of all strings where number a’s and b’s are equal.

Example = {λ , ab, ba, aabb, bbaa, aaabbb…….}

This given language is a DCFL because it has only infinite comparison and we can process it by stack using push and pop will be cleared.  (For detailed analysis follow chapter Example 2)

Corresponding grammar:

Now we assume the corresponding grammar is : S → aSb | bSa | λ

[Where aSb - same no. of a’s and b’s, bSa - same no. of b’s and a’s, λ – smallest string]

Initially, this grammar looks okay but some strings which are actual accepted by the machine not possible to generate from this grammar like abba, baab - how to derive it?

We can derive this string by 

Same as baab. So, we have to add one more function, SS

S → aSb | bSa | λ | SS 

So, this is final and right grammar for ${\mathbf{n}}_{\mathbf{a}}\mathbf{\left(}\mathbf{\omega }\mathbf{\right)}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{n}}_{\mathbf{b}}\mathbf{\left(}\mathbf{\omega }\mathbf{\right)}$

7.  Write the grammar of the following given language

Solution:

Now first we have to understand the language. 

It says “Set of all strings with an equal number of a’s and b’s and another condition if we take any prefix from a string, this prefix has number of a’s ≥ number of b’s.”

Note: For the basic concept of prefix see chapter Basic knowledge of string

This given language is DCFL because it has two infinite comparisons but not at a time. 

Let take an example:

ω = abba it follows ${\mathbf{n}}_{\mathbf{a}}\mathbf{\left(}\mathbf{\omega }\mathbf{\right)}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{n}}_{\mathbf{b}}\mathbf{\left(}\mathbf{\omega }\mathbf{\right)}$

Now we are going to check is it following the second condition. 

ω = abba

λ.abba      (right)    [Here we take λ as a prefix and condition satisfy]

a.bba       (right)     [Here we take a as a prefix and condition satisfy]

ab.ba      (right)     [Here we take ab as a prefix and condition satisfy] 

abb.a     (wrong)   [Here we take abb as a prefix and but the condition is not satisfied because the number of  a’s is less number of b’s in this prefix which is not meet the second condition.]

So, this string is not in L.

Corresponding grammar:

Now we condition the first condition ${\mathbf{n}}_{\mathbf{a}}\mathbf{\left(}\mathbf{\omega }\mathbf{\right)}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{n}}_{\mathbf{b}}\mathbf{\left(}\mathbf{\omega }\mathbf{\right)}$ so, we already discuss this grammar in the previous example i.e. S → aSb | bSa | λ | SS. 

Now, what should be the modification of this grammar where we can meet the second condition.

For the given language,

S → aSb | bSa | λ | SS

Here aSb does not make any problem for the second condition but bSa makes some problems where ${\mathbf{n}}_{\mathbf{a}}\mathbf{\left(}\mathbf{v}\mathbf{\right)}\mathbf{ }\mathbf{\ge }\mathbf{ }{\mathbf{n}}_{\mathbf{b}}\mathbf{\left(}\mathbf{v}\mathbf{\right)}$ is failed. So, we removed bSa from production.

S → aSb | SS | λ

Example:

So, this grammar S → aSb | SS | λ is the final grammar for this given language.

Important Point:

This CFG S → aSb | SS | λ is very interesting grammar because also usedfor checking balanced patterns is in programming.

Lets a = (and  b = )

S → (S) | SS | λ               [(S) means first (and then)]

In programming language balanced parenthesis means ( ≥ )