Which of the following properties correctly describe a Regular Grammar? (A)…
2024
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 grammar 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:
- A.
(A) and (B) Only
- B.
(B) and (C) Only
- C.
(C) and (D) Only
- D.
(A) and (C) Only.
Attempted by 129 students.
Show answer & explanation
Correct answer: D
Answer: The correct properties are the ones that state the production-rule form and the correspondence with finite automata.
Production rules are of the form A → xB or A → x, where A and B are non-terminals and x is a terminal. This describes a right-linear regular grammar; some definitions also permit an empty-string (ε) production.
There is a direct correspondence between regular grammars and finite automata: every regular grammar generates a regular language that can be recognised by a finite automaton, and for every finite automaton there is an equivalent regular grammar.
Why the other statements are false:
The claim that regular grammars are more powerful than context-free grammars is false. Regular grammars are strictly less expressive: every regular language is context-free, but there are context-free languages (for example, { a^n b^n | n ≥ 0 }) that are not regular.
The claim that regular grammars can generate languages not recognised by any type of automata is false. By definition, languages generated by regular grammars are exactly the languages recognised by finite automata (a specific class of automata).
Therefore, the correct selection is the choice that picks the two statements described above: the production-rule form and the direct correspondence with finite automata.
A video solution is available for this question — log in and enroll to watch it.