开发者

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.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜