Nielit STA [02-12-2018]
October 18, 2023Programming
October 18, 2023UGC NET CS 2014 June-paper-2
| Question 9 |
The context free grammar for the language L = {anbmck | k = |n – m|,
n ≥ 0, m ≥ 0, k ≥ 0} is
n ≥ 0, m ≥ 0, k ≥ 0} is
| S → S1S3, S1 → aS1c | S2| λ, S2 → aS2b|λ, S3 → aS3b| S4 | λ, S4 → bS4c|λ | |
| S → S1S3, S1→ aS1S2c | λ, S2 → aS2b|λ, S3 → aS3b| S4 |λ, S4 → bS4c|λ | |
| S → S1|S2, S1→ aS1S2c | λ, S2 → aS2b | λ, S3 → aS3b | S4 |λ, S4 → bS4c|λ | |
| 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.
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.
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 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.
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.
Subscribe
Login
0 Comments