GATE 2003
December 16, 2023Question 8421 – Algorithms
December 16, 2023GATE 2003
| Question 15 |
If the strings of a language L can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true?
| L is necessarily finite
| |
| L is regular but not necessarily finite | |
| L is context free but not necessarily regular | |
| L is recursive but not necessarily context free |
Question 15 Explanation:
The given language L is to be recursively enumerable. The TM which accepts the language which is in lexicographic order. If the language is not in lexicographic order which is not accepted by TM.
The give ‘L’ is recursive but not necessarily context free.
The give ‘L’ is recursive but not necessarily context free.
Correct Answer: D
Question 15 Explanation:
The given language L is to be recursively enumerable. The TM which accepts the language which is in lexicographic order. If the language is not in lexicographic order which is not accepted by TM.
The give ‘L’ is recursive but not necessarily context free.
The give ‘L’ is recursive but not necessarily context free.