CODEWITHSUNDEEP
formal-languages
AruniRC
AruniRC

Reputation: 5148

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 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.

Upvotes: 2

Views: 2271

Answers (2)

Armen Tsirunyan
Armen Tsirunyan

Reputation: 132974

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

Upvotes: 2

hfs
hfs

Reputation: 2593

Another hint: Write all your production rules such that they guarantee Na(w) = Nb(w) at every step.

Upvotes: 1

Related Questions