in Theory of Computation
219 views
0 votes
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$,

where

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

and

                                                                            $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
219 views

Please log in or register to answer this question.

Related questions