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
Also check: Importance of finite automata
(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 a palindrome.
Thus we can write the language of the grammar L(G) = {wwR : w ∈ {a, b}*};
Also check: keywords in c
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}
Also check: software process improvement
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
Also check: software engineering vs system engineering
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}*}
Also check: define automata
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}
Also check: convert nfa to dfa
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}
Also check: power of alphabet in automata
Thanks