Discussion
Which of the following production forms belongs to unrestricted grammar (Type 0) :
(i) S → ASA A → BCa BC → Aa
(ii) S → aSa/∈
(iii) BSA → aSb/ASB, A → aB/b B → Bb/a
Answer: D
All three belong to unrestricted grammars, so the answer is (i), (ii) and (iii) only.
A Type 0 (unrestricted) grammar allows productions \(\alpha \rightarrow \beta\) where \(\alpha\) is any string containing at least one non-terminal and \(\beta\) is any string. Every production in the three sets has a non-terminal on its left-hand side, including the context-sensitive looking BC → Aa and BSA → aSb, and the context-free S → aSa/∈.
Because the Chomsky hierarchy is nested, context-free and context-sensitive productions are also Type 0, so no set is excluded and the narrower options are wrong.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development