79.6k views
2 votes
Let L be any r.e. language. We know that there is an unrestricted grammar for L. Show that L can be generated by an unrestricted grammar in which the left side of every production has no terminal. Hint: provide an algorithm to convert an unrestricted grammar to the desired form.

User Marquis
by
6.0k points

1 Answer

7 votes

Answer:

Step-by-step explanation:

Find attached

Let L be any r.e. language. We know that there is an unrestricted grammar for L. Show-example-1
Let L be any r.e. language. We know that there is an unrestricted grammar for L. Show-example-2
User Ekalin
by
6.7k points