2
$\begingroup$

In the book of Hopcroft-Ullman (the 1979 edition) there is a rule $Da\rightarrow aaD$ in the example of the CSL language $a^{2^i}$.

Valid rules in CSG have the form $\alpha A \beta\rightarrow \alpha\psi\beta$. I think the mentioned rule is not valid, since there is no way to get rid of the terminal $a$ at the right side.

Or is there some magic that escapes me?

$\endgroup$

1 Answer 1

2
$\begingroup$

What Hopcroft and Ullman call a context-sensitive grammar is nowadays called a noncontracting grammar; see page 223. The two types of grammar are equivalent in power.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.