开发者

Production rules for a grammar

开发者 https://www.devze.com 2023-04-03 18:12 出处:网络
Before anything, yes, this is from coursework and I\'ve been at it sporadically while dealing with another project.

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

精彩评论

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