4
$\begingroup$

wikipedia states:

Every Post canonical system can be reduced to a string rewriting system (semi-Thue system). [...]

It has been proved that any Post canonical system is reducible to such a substitution system, which, as a formal grammar, is also called a phrase-structure grammar, or a type-0 grammar in the Chomsky hierarchy.

And on a different page it says:

A semi-Thue system is also a special type of Post canonical system, but every Post canonical system can also be reduced to an SRS.

I have not been able to find a good explanation of these statements.

Is there a good reference that shows how to do conversions between these notions?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.