Which of the following properties correctly describe a Regular Grammar?
(A) All production rules are of the form A → xB or A → x, where A and B are non-terminal symbols and x is a terminal symbol.
(B) Regular grammars are more powerful than context-free grammars and can express any type of language.
(C) There is a direct correspondence between regular grammars and finite automata.
(D) Regular grammars can generate languages that are not recognised by any type of automata.
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: D. (A) and (C) Only
Explanation
A is the (right-linear) form of a regular grammar and C is true, since regular grammars and finite automata define the same class. Regular grammars are the weakest in the Chomsky hierarchy (B false), and their languages are recognised by finite automata (D false).More Theory of Computation and Compilers questions
- If L₁ and L₂ are context-free languages, which one of the following is true about L₁ ∩ L₂?
- Which of the following tasks could be attained using syntax trees in compiler design? (A) Type Checking (B) Code Generation (C) Code Optimi…
- Arrange the following stages of a Turing Machine (TM) operation in the correct order as they occur during computation. (A) Writing a symbol…
- Which of the following languages can be recognized by a Non-Deterministic Finite Automaton (NFA) but cannot be recognized by a Deterministi…
- Arrange the following phases in the correct order as they typically occur in the compilation process. (A) Lexical Analysis (B) Semantic Ana…
- Arrange the following language classes in ascending order of their expressive power, as defined by the Chomsky hierarchy: (A) Context-free…