Talk:Regular grammar
From Wikipedia, the free encyclopedia
I have taken the liberty to disntnguish between right regular grammars and left regular grammars more clearly -- rp, mar 09 2004
It would be nice to give a sense of what (N, Σ, P, S) are without sending readers immediately to Formal_grammar. Is there a way to do this that would make sense? Jodi.a.schneider 04:01, 10 October 2006 (UTC)
[edit] Regular Grammar
On some books left regular grammar is defined as below
A → a* - where A is a non-terminal in N and a is a terminal in Σ A → Ba* - where A and B are in N and a is in Σ
However in Wikipedia the definition has excluded the possibility of having more than one terminals on the right hand side of the production. Why is this difference?
For what I know there is no real difference: the grammars showed on the page are "strongly" (or "strictly") linear, while the ones you report are just linear (even if the way you wrote them is not so clear to me, because if you write a* it could mean "0 or more instances of the same symbol (the one which 'a' refers to)", and that wouldn't mean "regular" because it could produce an infinite sequence: in BNF you would use recursion to mean that, and you'd get something like A → B A for the second rule, which makes the grammar absolutely not regular). From a linear grammar you can always get its strictly linear equivalent by substituting the non-strict rules with sets of rules each of which produce at most a terminal symbol (i.e., each rule does only one step). Sorry for my English, anyway... and if I said something wrong let me know! :-) --Ma82 12:12, 2 September 2006 (UTC)
if you write a* it could mean 0 or more instances of the same symbol and that wouldn't mean "regular" because it could produce an infinite sequence
No. You can have more than one terminal on the right side. Every Formal Languages and Automata book states this.
However, you cannot write the production as:
A → a*
You can have multiple terminals on the right-side of the production. And in the case of a language consisting of a*, you could use the following productions to generate the language:
A → aA
A → ε
which is completely legal and can produces valid string of infinite length for the regular language L = {a* | a is an element of Σ = {a}*}.
The issue here is you're not writing the production, you're giving the form for the production. And productions can be of the form both shown in the current article and seen below:
right-linear:
S → abS | aba
left-linear:
S → Aaba
A → Aab | B
B → ε
Where each production contains at most one Variable that is contained in N and zero or more Terminals that are an element of the language Σ*. Both grammars produce the regular language ab(ab)*a and are valid forms of the right-linear and left-linear regular grammars.
The way this page is set up right now, it looks like you cannot produce a right or left grammar for a regular language containg an infinite amount of strings, such as a*, b*, (ab)*, a*b*, (a + b)*, etc.
--Sparkticus 17:59, 25 October 2006 (UTC)
