###### Nielit STA [02-12-2018]

October 18, 2023###### Programming

October 18, 2023# UGC NET CS 2014 June-paper-2

Question 9 |

The context free grammar for the language L = {a

n ≥ 0, m ≥ 0, k ≥ 0} is

^{n}b^{m}c^{k}| k = |n – m|,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}c|S_{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

Option(B): Option(B) will generate the string “acab” which does not belongs to the sequence a

Option(C): In this option production S

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

Option(B): Option(B) will generate the string “acab” which does not belongs to the sequence a

Option(C): In this option production S

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