Which of the following is -free grammar?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: B. Type-1
Explanation
Type-1 rules must satisfy |α| ≤ |β|, so a rule can never shrink a string to ε (apart from the special S → ε case). Type-0, Type-2 and Type-3 grammars all allow ε-productions.
Note on the official key: the official key says option D. Official/PW key is D (Type-3). Regular grammars may contain A → ε; context-sensitive (Type-1) grammars are the non-contracting, ε-free class.
More Theory of Computation and Compilers questions
- While processing a string by an LR parser, the reading of the given string by the parser is-
- What is the minimum and maximum number of initial, dead, unreachable and final states in a n valid ' ' state finite automaton, where the φ…
- Which of the following finite automata recognize L = {a, b}*? (Transition tables A–D are shown; in each, the start state q0 is accepting.)
- Match List I with List II
- Consider the following statements: (A) For every regular language, we can design Turing Machine (B) For every context free language, we can…
- The transition function ' ' in multi-tape Turing machine is defined as: