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 Jul 17 '16 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 Jul 17 '16 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 Jul 17 '16 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 Dec 6 '17 at 22:50

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

| cite | improve this answer | |

Your Answer

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

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