Example 1:

For the grammar given below, find out the context free language. The grammar G = ({S}, {a, b}, S, P) with the productions are;

S → aSa,           (Rule: 1)
S → bSb            (Rule: 2)
S →  ε               (Rule: 3)

Solution:

First compute some strings generated by  the production rules of the grammar G in the above;

(i)            S ⇒ aSa,                (Rule: 1)
⇒ aεa,               (Rule: 3)
i.e.          ⇒ aa

(ii)           S ⇒ bSb,                (Rule: 2)
⇒ bεb,               (Rule: 3)
i.e.          ⇒ bb

(iii)          S ⇒ aSa,                (Rule: 1)
⇒ abSba,           (Rule: 2)
⇒ abεba            (Rule: 3)
i.e.          ⇒ abba

(iv)         S ⇒ bSb,                (Rule: 2)
⇒ baSab,           (Rule: 1)
⇒ ba ε ab         (Rule: 3)
i.e.          ⇒ baab

(v)          S ⇒ aSa,                (Rule: 1)
⇒ aaSaa,           (Rule: 1)
⇒ aabSbaa,      (Rule: 2)
⇒ aabbSbbaa, (Rule: 2)
⇒ aabb ε bbaa (Rule: 3)
i.e.          ⇒ aabbbbaa

Hence; Language generated by the above grammar L(G) = {aa, bb, abba, baab, aabbaa, aabbbbaa,.. .. .. .. }

By analyzing the above generated string form the grammar G, there has a similar pattern in all computed strings, i.e.

• The length of the string is even always i.e. length of the string L(w) ≥ 2 × i | i = 1, 2, 3, 4.. .
• From the half length of the string, string is the reverser of each other side i.e. string is generated by the language is palindrome.

Thus we can write the language of the grammar L(G) = {wwR : w ∈ {a, b}*};

Example 2: For the grammar given below, find out the context free language. The grammar G = ({S}, {a, b}, S, P) with the productions are;

S → abB,           (Rule: 1)
A → aaBb          (Rule: 2)
A →  ε               (Rule: 3)
B → bbAa          (Rule: 4)

Solution:

First compute some strings generated by  the production rules of the grammar G in the above;

(i)            S ⇒ abB,              (Rule: 1)
⇒ ab bbAa        (Rule: 4)
⇒ ab bb ε a      (Rule: 3)
i.e.          ⇒ ab bba

(ii)           S ⇒ abB,                           (Rule: 1)
⇒ ab bbAa                     (Rule: 4)
⇒ ab bb aaBb a             (Rule: 2)
⇒ ab bb aa bbAa ba       (Rule: 4)
⇒ ab bb aa bb ε a ba      (Rule: 3)
i.e           ⇒ ab bb aa bba ba

(iii)          S ⇒ abB,                                                      (Rule: 1)
⇒ ab bbAa                                                (Rule: 4)
⇒ ab bb aaBb a                                         (Rule: 2)
⇒ ab bb aa bbAa ba                                   (Rule: 4)
⇒ ab bb aa bb aaBb a ba                            (Rule: 2)
⇒  ab bb aa bb aa bbAa b a ba                    (Rule: 4)
⇒  ab bb aa bb aa bb ε a b a ba                   (Rule: 3)
i.e           ⇒  ab bb aa bb aa bba ba ba
(iv)         S ⇒ abB,                                                                               (Rule: 1)
⇒ ab bbAa                                                                        (Rule: 4)
⇒ ab bb aaBb a                                                               (Rule: 2)
⇒ ab bb aa bbAa ba                                                       (Rule: 4)
⇒ ab bb aa bb aaBb a ba                                              (Rule: 2)
⇒  ab bb aa bb aa bbAa b a ba                                    (Rule: 4)
⇒  ab bb aa bb aa bb aaBb a ba ba                            (Rule: 2)
⇒  ab bb aa bb aa bb aa bbAa ba ba ba                    (Rule: 4)
⇒  ab bb aa bb aa bb aa bb ε a ba ba ba                   (Rule: 3)
i.e           ⇒  ab bb aa bb aa bb aa bba ba ba ba

Hence; Language generated by the above grammar L(G) =   { ab bba  (minimum string)
ab bb aa bba ba
ab bb aa bb aa bba ba ba
ab bb aa bb aa bb aa bba ba ba ba

}
By analyzing the above generated string form the grammar G, there has a similar pattern in all computed strings, i.e.

• The minimum length of the string consist ab bba always.
• After obtained the minimum string there have some repetition of strings comes i.e. the loop of string (bb aa and ba) comes finite times. (Note: Highlighted by underlined strings)

Thus we can write the language of the grammar L(G) = {ab (bb aa)n bba (ba)n : n ≥ 0}

Example 3:

For the grammar given below, find out the context free language. The grammar G = ({S}, {a, b, c}, S, P) with the productions are;

S → aSa,               (Rule: 1)
S → bSb                (Rule: 2)
S →  c                   (Rule: 3)

Solution:

First compute some strings generated by the production rules of the grammar G in the above;

(i)            S ⇒ aSa,                (Rule: 1)
⇒ aca,                (Rule: 3)
i.e.          ⇒ aca

(ii)           S ⇒ bSb,                (Rule: 2)
⇒ bcb,                (Rule: 3)
i.e.          ⇒ bcb

(iii)          S ⇒ aSa,                (Rule: 1)
⇒ aaSaa,           (Rule: 1)
⇒ aacaa,           (Rule: 3)
i.e.          ⇒ aacaa

(iv)         S ⇒ aSa,                (Rule: 1)
⇒ abSba,           (Rule: 2)
⇒ abcba,           (Rule: 3)
i.e.          ⇒ abcba

(v)          S ⇒ bSb,                (Rule: 2)
⇒ baSab,           (Rule: 1)
⇒ bacab,           (Rule: 3)
i.e.          ⇒ bacab

(vi)         S ⇒ aSa,                (Rule: 1)
⇒ aaSaa,           (Rule: 1)
⇒ aabSbaa,      (Rule: 2)
⇒ aabcbaa,      (Rule: 3)
i.e.          ⇒ aabcbaa

Hence; Language generated by the above grammar L(G) = {c, aca, bcb, aacaa, abcba, aacaa, bbcbb, aabcbaa,.. .. .. .. }

By analyzing the above generated string form the grammar G, there has a similar pattern in all computed strings, i.e.

• The length of the string is odd always i.e. length of the string L(w) ≥ 1, 3, 5, 7, 9 .. .. ..
• From the middle symbol of the string i.e. ‘c’, string is the reverser of each other side i.e. string is generated by the language is palindrome.

Thus we can write the language of the grammar L(G) = {wcwR : w ∈ {a, b}*}

Example 4: For the grammar given below, find out the context free language. The grammar G = ({S}, {a}, S, P) with the productions are;

S → SS                   (Rule: 1)
S → a                     (Rule: 2)
Solution:

First compute some strings generated by the production rules of the grammar G in the above;

(i)            S ⇒ a                    (Rule: 2)

(ii)           S ⇒ SS                   (Rule: 1)
⇒ aS,                  (Rule: 2)
⇒ aa,                  (Rule: 2)
i.e.          ⇒ aa   ⇒ a2

(iii)          S ⇒ SS                   (Rule: 1)
⇒ aS                   (Rule: 2)
⇒ aSS                 (Rule: 1)
⇒ aaS                 (Rule: 2)
⇒ aaa                 (Rule: 2)
i.e.          ⇒ aaa ⇒ a3

Hence; Language generated by the above grammar L(G) = {a, a2, a3, a4, a5, .. .. .. .. }

By analyzing the above generated string form the grammar G, there has a similar pattern in all computed strings, i.e.

• The minimum length of the string is one.
• The number of occurrence of a’s is increase one by one.

Thus we can write the language of the grammar L(G) = {an : n ≥ 1}

Example 5: For the grammar given below, find out the context free language. The grammar G = ({S}, {a, b }, S, P) with the productions are;

S → aSb,               (Rule: 1)
S → ab                   (Rule: 2)

Solution:

First compute some strings generated by the production rules of the grammar G in the above;

(i)            S ⇒ ab,                 (Rule: 2)

(ii)           S ⇒ aSb,                (Rule: 1)
⇒ aabb,             (Rule: 2)
i.e.          ⇒ aabb ⇒ a2b2

(iii)          S ⇒ aSb,                (Rule: 1)
⇒ aaSbb,           (Rule: 1)
⇒ aaabbb,        (Rule: 2)
i.e.          ⇒ aaabbb ⇒ a3b3

(iv)         S ⇒ aSb,                (Rule: 1)
⇒ aaSbb,           (Rule: 1)
⇒ aaaSbbb,      (Rule: 1)
⇒ aaaabbbb,    (Rule: 2)
i.e.          ⇒ aaaabbbb ⇒ a4b4

(v)          S ⇒ aSb,                                (Rule: 1)
⇒ aaSbb,                           (Rule: 1)
⇒ aaaSbbb,                      (Rule: 1)
⇒ aaaaSbbbb,                 (Rule: 1)
⇒ aaaaabbbbb,               (Rule: 2)
i.e.          ⇒ aaabbb ⇒ a5b5

Hence; Language generated by the above grammar L(G) = {ab, a2b2,  a3b3, a4b4,  a5b5, a6b6,  a7b7,.. .. .. .. }

By analyzing the above generated string form the grammar G, there has a similar pattern in all computed strings, i.e.

• The length of the string is greater than or equal to 2.
• Number of a’s and b’s are equal.
• Presence of a’s followed by b’s.

Thus we can write the language of the grammar L(G) = {anbn : n ≥ 1}

This site uses Akismet to reduce spam. Learn how your comment data is processed.