Discussion
Which of the following is/are correct statement(s) :
(i) A language L is said to be a deterministic context free language if and only if there exists a deterministic ρDA M such that : L = L(M)
(ii) If every grammar that generates L is ambiguous, then the language is called inherently ambiguous.
(iii) A CFG is in Greibach Normal Form if all productions in G have the form A → BC and A → a where A, B, C are non-terminals and a is a terminal.
Answer: C
The correct statements are (i) and (ii) only.
Statement (i), read with the printed 'ρDA' as PDA (pushdown automaton), is the definition of a deterministic context-free language: one accepted by some deterministic PDA. Statement (ii) is the definition of an inherently ambiguous language: every grammar generating it is ambiguous.
Statement (iii) is wrong: productions of the form A → BC and A → a define Chomsky Normal Form. In Greibach Normal Form every production has the form A → aα, a terminal followed by a string of non-terminals.
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