1 votes 1 votes Regular grammar can be of form :- A->tV or A->Vt or A->t where t is terminal and V is variable. Here is t string of terminals or a single terminal? I am seeing different definitions of terminal everywhere. Theory of Computation theory-of-computation regular-grammar + – Xylene asked Jul 12, 2017 Xylene 705 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 1 votes 1 votes A regular grammar is either right linear or left linear. Right Linear: If all the productions are of the form S $\rightarrow$ aA S $\rightarrow$ a Where A $\in$ V (set of variable) and a $\in$ $\sum$ * Left Linear: If all the production are of the form S $\rightarrow$ Aa S $\rightarrow$ a Where A $\in$ V (set of variable) and a $\in$ $\sum$ *. Note: If we have this kind of production in a grammar then it is neither the right linear nor the left linear. Hence it is not a regular grammar. S $\rightarrow$ aA S $\rightarrow$ Aa S $\rightarrow$ a. Where A $\in$ V (set of variable) and a $\in$ $\sum$ *. Hemant Parihar answered Jul 12, 2017 • selected Jul 12, 2017 by Xylene Hemant Parihar comment Share Follow See all 4 Comments See all 4 4 Comments reply Xylene commented Jul 12, 2017 reply Follow Share I read this definition and according to this definition we can have only a single terminal on RHS of the production right? 0 votes 0 votes Hemant Parihar commented Jul 12, 2017 reply Follow Share @Xylene yes at the right side we can have only a single terminal. 1 votes 1 votes Xylene commented Jul 12, 2017 reply Follow Share Even I thought the same, but according to this link it seems we can have more than one terminals http://www.cs.colostate.edu/~massey/Teaching/cs301/RestrictedAccess/Slides/301lecture05.pdf Please confirm and let me know. 0 votes 0 votes Hemant Parihar commented Jul 12, 2017 reply Follow Share @Xylene, yes you are correct. We can have more than one terminals. I verified it from Peter linz. There also they have used more than one terminals at the right side. Having more than one terminal doesn't effect too much. We can always convert it such that right side is single terminal. For ex: S $\rightarrow$ abc. You can convert this like, S $\rightarrow$ aA A $\rightarrow$ bB B $\rightarrow$ c. But yes definition is the definition and we should follow the definition. So yes we can have more than one terminal at the right side. 1 votes 1 votes Please log in or register to add a comment.
1 votes 1 votes proper defination regular grammar will be- V -> T*V+T*(right linear grammar) or V-> VT*+T*(left linear grammmar) Prateek Raghuvanshi answered Jul 13, 2017 Prateek Raghuvanshi comment Share Follow See all 0 reply Please log in or register to add a comment.