Arrange the following families of languages from specialization to generalization, defined over alphabet Σ:
A. Family of all regular languages
B. Family of all Turing acceptable languages
C. Family of all Turing decidable languages
D. Family of all context free languages
Choose the correct answer from the options given below:
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. A, D, C, B
Explanation
By the Chomsky hierarchy and computability theory, every regular language is context-free, every context-free language is Turing-decidable, and every Turing-decidable language is Turing-acceptable (recursively enumerable) — each class strictly contains the previous one. So from most specialized (smallest class) to most general (largest class), the order is Regular ⊂ Context-free ⊂ Turing-decidable ⊂ Turing-acceptable, i.e. A, D, C, B.More Theory of Computation and Compilers questions
- Which of the following statements is incorrect?
- The minimum state DFA of the following would be the following: (a DFA with states q0 (start), q1, q2, q3 and q4 (accepting) is given, with…
- Find the Follow (A) & Follow (C).
- In the LL(1) Parsing table of the given CFG, how many valid non-blank entries will be there in the rows for variables 'B' and 'D'?
- Identify the correct statement from the following.
- What will be the FIRST(S) & FIRST(D)?