Different Grammars

Question 1

What is unrestricted ‘type 0’ grammar

Answer 1

Productions have strings of variables on each side of the production rather than just one variable on the LHS like CFG

Question 2

When is a language L turing-acceptable

Answer 2

If and only if it is generated by an unrestricted grammar

Question 3

What is a context-sensitive grammar

Answer 3

The productions never make strings shorter

S-> epsilon is permitted where S neever appears on the RHS

Question 4

What is non-contracting grammars

Answer 4

There are at >= elements on the RHS as on the LHS

The productions never make strings shorter