regular/context free grammar

Question

Im hoping someone can help me understand a question I have, its not homework, its just an example question I am trying to work out. The problem is to define a grammar that generates all the sums of any number of operands. For example, 54 + 3 + 78 + 2 + 5... etc. The way that I found most easy to define the problem is:

non-terminal {S,B}
terminal {0..9,+,epsilon}

Rules:

S -> [0..9]S
S -> + B
B -> [0..9]B
B -> + S
S -> epsilon
B -> epsilon 

epsilon is an empty string.

This seems like it should be correct to me as you could define the first number recursively with the first rule, then to add the next integer, you could use the second rule and then define the second integer using the third rule. You could then use the fourth rule to go back to S and define as many integers as you need.

This solution seems to me to be a regular grammar as it obeys the rule A -> aB or A -> a but in the notes it says for this question that it is no possible to define this problem using a regular grammar. Can anyone please explain to me why my attempt is wrong and why this needs to be context free?

Thanks.

Please first notice that, in your grammar, there may be a hanging + on the right side. If the first B is empty, then 1+ is a valid sentence, which I don't think is what you're intending. — paulotorrens

paulotorrens paulotorrens · Accepted Answer · 2014-12-28T03:06:48

Although it's not the correct definition, it's easier to think that for a language to be non-regular it would need to balance something (like parenthesis).

Your problem can be solved using direct recursion only on the sides of the rules, not in the middle, so it can be solved using a regular language. (Again, this is not the correct definition, but it's easier to remember!)

For example, for a regular expression engine (like in Perl or JavaScript) one could easily write /(\d+)(\+(\d+))*/.

You could write it this way:

non-terminal {S,R,N,N'}
terminal {0..9,+,epsilon}

Rules:

S -> N R
S -> epsilon

N -> [0..9] N'
N' -> N
N' -> epsilon

R -> + N R
R -> epsilon

Which should work correctly.

regular/context free grammar

2 Answers