Production rules for a grammar
Before anything, yes, this is from coursework and I've been at it sporadically while dealing with another project.
A language consists of those strings (of terminals 'a' and 'b') where the number of a = number of b. Trying to find the production rules of the grammar that will开发者_C百科 define the above language.
More formally, L(G) = {w | Na(w) = Nb(w)}
So i guess it should go something like, L = {ϵ, ab, aabb, abab, abba, bbaa, ... and so on }
Any hints, or even related problems with solution would do which might help me better grasp the present problem.
I think this is it:
S -> empty (1)
S -> aSb (2)
S -> bSa (3)
S -> SS (4)
Edit: I changed the rules. Now here's how to produce bbaaabab
S ->(4) SS ->(4) SSS ->(3) bSaSS ->(3) bbSaaSS -> (1)bbaaSS
->(2) bbaaaSbS ->(2) bbaaaSbaSb ->(1)bbaaabaSb ->(1) bbaaabab
Another hint: Write all your production rules such that they guarantee Na(w) = Nb(w) at every step.
精彩评论