Nielit STA [02122018]
October 18, 2023Programming
October 18, 2023UGC NET CS 2014 Junepaper2
Question 9

The context free grammar for the language L = {a^{n}b^{m}c^{k}  k = n – m,
n ≥ 0, m ≥ 0, k ≥ 0} is
n ≥ 0, m ≥ 0, k ≥ 0} is
S → S_{1}S_{3}, S_{1} → aS_{1}c  S_{2} λ,
S_{2} → aS_{2}bλ, S_{3 }→ aS_{3}b S_{4}  λ, S_{4} → bS_{4}cλ 

S → S_{1}S_{3}, S_{1}→ aS_{1}S_{2}c  λ,
S_{2} → aS_{2}bλ, S_{3} → aS_{3}b S_{4} λ, S_{4} → bS_{4}cλ 

S → S_{1}S_{2}, S_{1}→ aS_{1}S_{2}c  λ,
S_{2} → aS_{2}b  λ, S_{3} → aS_{3}b  S_{4} λ, S_{4} → bS_{4}cλ 

S → S_{1}  S_{3}, S_{1}→ aS_{1}cS_{2}  λ,
S_{2} → aS_{2}b  λ, S_{3} → a S_{3}b S_{4}  λ, S_{4} → bS_{4}c  λ 
Question 9 Explanation:
L = { λ, ab, ac, bc, aabb,aabc,aac, bbc, ……..}
Option(A): Option(A) will generate the string “acab” which does not belongs to the sequence a^{n}b^{m}c^{k} . So, it is not the context free grammar for the language L.
Option(B): Option(B) will generate the string “acab” which does not belongs to the sequence a^{n}b^{m}c^{k}. So, it is not the context free grammar for the language L.
Option(C): In this option production S_{3} and S_{4} are unreachable so it is not the context free grammar for the language L.
Option (D): The grammar given in this option can generate { λ, ab, ac, bc, aabb,aabc,aac, bbc, ……..}. So it is the context free grammar for the language L.
Option(A): Option(A) will generate the string “acab” which does not belongs to the sequence a^{n}b^{m}c^{k} . So, it is not the context free grammar for the language L.
Option(B): Option(B) will generate the string “acab” which does not belongs to the sequence a^{n}b^{m}c^{k}. So, it is not the context free grammar for the language L.
Option(C): In this option production S_{3} and S_{4} are unreachable so it is not the context free grammar for the language L.
Option (D): The grammar given in this option can generate { λ, ab, ac, bc, aabb,aabc,aac, bbc, ……..}. So it is the context free grammar for the language L.
Correct Answer: D
Question 9 Explanation:
L = { λ, ab, ac, bc, aabb,aabc,aac, bbc, ……..}
Option(A): Option(A) will generate the string “acab” which does not belongs to the sequence a^{n}b^{m}c^{k} . So, it is not the context free grammar for the language L.
Option(B): Option(B) will generate the string “acab” which does not belongs to the sequence a^{n}b^{m}c^{k}. So, it is not the context free grammar for the language L.
Option(C): In this option production S_{3} and S_{4} are unreachable so it is not the context free grammar for the language L.
Option (D): The grammar given in this option can generate { λ, ab, ac, bc, aabb,aabc,aac, bbc, ……..}. So it is the context free grammar for the language L.
Option(A): Option(A) will generate the string “acab” which does not belongs to the sequence a^{n}b^{m}c^{k} . So, it is not the context free grammar for the language L.
Option(B): Option(B) will generate the string “acab” which does not belongs to the sequence a^{n}b^{m}c^{k}. So, it is not the context free grammar for the language L.
Option(C): In this option production S_{3} and S_{4} are unreachable so it is not the context free grammar for the language L.
Option (D): The grammar given in this option can generate { λ, ab, ac, bc, aabb,aabc,aac, bbc, ……..}. So it is the context free grammar for the language L.
Subscribe
Login
0 Comments