Arrange the following language classes in ascending order of their expressive power, as defined by the Chomsky hierarchy:
(A) Context-free languages
(B) Context-sensitive languages
(C) Regular languages
(D) Unrestricted grammars (recursively enumerable)
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: A. (C), (A), (B), (D)
Explanation
Regular ⊂ context-free ⊂ context-sensitive ⊂ recursively enumerable (unrestricted).More Theory of Computation and Compilers questions
- Which of the following are context-free languages? (A) {wⁱ xʲ yᵏ zˡ | i + k = j + l, where i, j, k, l ≥ 0} (B) {wⁱ xʲ yᵏ zˡ | i = j, k = l,…
- Let L = {ab, aa, baa}. Which of the following strings is NOT in L*?
- Let A = {a, b} and L = A*. Let X = {aⁿbⁿ | n > 0}. The languages L ∪ X and X are respectively:
- Which of the following symbol-table implementations is best suited if access time is to be minimum?
- Consider the grammar E → E + n | E × n | n. For the sentence n + n × n, the handles in the right-sentential forms of the reduction are:
- One of the purposes of using intermediate code in compilers is to: