Talk:Regular grammar
From Wikipedia, the free encyclopedia
 |
This article is within the scope of the WikiProject Philosophy, which collaborates on articles related to philosophy. To participate, you can edit this article or visit the project page for more details. | ||||||||
| ??? | This article has not yet received a rating on the quality scale. | ||||||||
| ??? | This article has not yet received an importance rating on the importance scale. | ||||||||
|
|||||||||
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)
[edit] prefix grammar
I just tripped over the article prefix grammar, which is almost nearly a left regular grammar, but not quite. I think that a prefix grammar can be described so that its isomorphic to a left regular grammar, but I'm not expert enough to try to guess how, off the top of my head. Clarification in both articles would be appreciated. linas 21:07, 21 April 2007 (UTC)
[edit] Question on claim in article
- Every context-free grammar can be easily rewritten into a form in which only a combination of left regular and right regular rules is used. Therefore, such grammars can express all context-free languages. Regular grammars, which use either left-regular or right-regular rules but not both, can only express a smaller set of languages, called the regular languages. In that sense they are equivalent with finite state automata and regular expressions. (for illustration: the paradigmatic context-free language with strings of the form aibi is generated by the grammar G with N = {S, A}, Σ = {a, b}, P with the rules
- S → aA
- A → Sb
- S → ε
- and S being the start symbol. Note that this grammar has both left-regular and right-regular rules and is therefore not regular any more.)
How do you express the language of valid bracket pairings in this setup? Seems to me you'd need to be able to replace one nonterminal with two to do that. Ben Standeven 04:44, 18 May 2007 (UTC)
Indeed. Grammars with a single nonterminal that are able to write terminals both to the left are called linear rammars, and are less powerful than the context-free grammars. They have a nice connection to push-down automata though: they can be accepted by PDA which make a single turn (from pushing to popping). One-sided linear grammars are then called left-linear and right-linear respectively depending on the side of the nonterminal. Jochgem 16:09, 31 October 2007 (UTC)
