Suppose we have unrestricted grammar but with restrictions on how rules are applied: we take first rule, search in string left to right and apply it as we go. If no match found, we proceed with second rule and so on. Else, if match(es) is found, we return to first rule and start of the string and start loop again.
I have 3 questions:
1. Have anybody studied transformations with similar rules?
2. Which machine accepts language corresponding to such grammars and rules?
3. How one can alter described algorithm to make deterministic Turing machine such a corresponding machine?

  • $\begingroup$ What do you mean by "match"? I can not tell if you are describing a generative process or a parsing algorithm, or if you are just redefining left-derivations. $\endgroup$
    – Raphael
    Commented Jul 17, 2016 at 12:11
  • $\begingroup$ It is definitely not (standard) leftmost derivation, because there we can choose which rules to apply, only place of application is determined. It is generative process. $\endgroup$
    – DSblizzard
    Commented Jul 17, 2016 at 12:55
  • $\begingroup$ I tried to read all I can find on link of unrestricted grammars and deterministic Turing machines and have not found anything useful. $\endgroup$
    – DSblizzard
    Commented Jul 17, 2016 at 12:56
  • $\begingroup$ The trick is to convert it to non-deterministic turing machine, and use a clause that allows to turn non-deterministic turing machine to deterministic (e.g. DFS) $\endgroup$
    – Ciantic
    Commented Dec 6, 2017 at 22:50

1 Answer 1


Such a grammar system is Turing-complete. I can encode a tag system, and tag systems are known to be Turing-complete.


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.