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?


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.