October 18, 2023
October 18, 2023
October 18, 2023
###### Programming
October 18, 2023
 Question 9
The context free grammar for the language L = {anbmck | k = |n – m|,
n ≥ 0, m ≥ 0, k ≥ 0} is
 A S → S1S3, S1 → aS1c | S2| λ, S2 → aS2b|λ, S3 → aS3b| S4 | λ, S4 → bS4c|λ B S → S1S3, S1→ aS1S2c | λ, S2 → aS2b|λ, S3 → aS3b| S4 |λ, S4 → bS4c|λ C S → S1|S2, S1→ aS1S2c | λ, S2 → aS2b | λ, S3 → aS3b | S4 |λ, S4 → bS4c|λ D S → S1 | S3, S1→ aS1c|S2 | λ, S2 → aS2b | λ, S3 → a S3b| S4 | λ, S4 → bS4c | λ
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 anbmck . 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 anbmck. So, it is not the context free grammar for the language L.
Option(C): In this option production S3 and S4 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.
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 anbmck . 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 anbmck. So, it is not the context free grammar for the language L.
Option(C): In this option production S3 and S4 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.