The Gateway to Computer Science Excellence
0 votes
A grammar $G = (V, T, S, P)$ is called $\text{unrestricted }$ if all the production are of the form

                                                                                 $u\rightarrow v$,

where $u$ is nit $(V\cup T)^+$ and $v$ is int $(V\cup T)^*$

Some authors give a definition of unrestricted grammars that is not quite the same as our Definition. In this alternate definition, the productions of an unrestricted grammar are required to be of the form

                                                                                 $x\rightarrow y$,


                                                                  $x\in (V\cup T)^*V(V\cup T)^*$,


                                                                            $y\in(V\cup T)^*$

The difference is that here the left side must have at least one variable.

Show that this alternate definition is basically the same as the one we use, in the sense that for every grammar of one type, there is an equivalent grammar of the other type.
in Theory of Computation by Boss (11.8k points) | 6 views

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,834 questions
57,750 answers
108,169 users