Aspire's Library
A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations - NIMCET
Study Stuff for MCA Examinations - NIMCET
Previous Year Question (PYQs)
Match List I with List II
Choose the correct answer from the options given below:
| List I | List II |
|---|---|
| A. $S\to XY,\ X\to 0,\ Y\to 1$ | I. Greibach Normal Form |
| B. $S\to aS\mid bSS\mid c$ | II. Context sensitive Grammar |
| C. $S\to AB,\ A\to 0A\mid 1A\mid 0,\ B\to 0A$ | III. Chomsky Normal Form |
| D. $S\to aAbc,\ Ab\to bA,\ Ac\to Bbcc,\ bB\to Bb,\ aB\to aa\mid aaA$ | IV. S-Grammar |
Solution
For A, productions are of the form $A\to BC$ or $A\to a$, so it is Chomsky Normal Form. Hence, $A-III$.For B, every production starts with a terminal symbol, so it is Greibach Normal Form. Hence, $B-I$.
For C, grammar is matched with S-Grammar. Hence, $C-IV$.
For D, some productions have more than one symbol on the left side, like $Ab\to bA$, and length is non-decreasing. So it is Context Sensitive Grammar. Hence, $D-II$.
Final matching is $A-III,\ B-I,\ C-IV,\ D-II$.
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
Ask Your Question or Put Your Review.
