Tips for creating "Context Free Grammar"

Question

I am new to CFG's,
Can someone give me tips in creating CFG that generates some language

For example

L = {am bn | m >= n}

What I got is:

So -> a | aSo | aS1 | e
S1 -> b | bS1 | e

but I think this area is wrong, because there is a chance that the number of b's can be greater than a's.

Chromomere

Answer 1

How to write CFG with example a^mbⁿ

L = {a^m bⁿ | m >= n}.

Language description: a^m bⁿ consist of a followed by b where number of a are equal or more then number of b.

some example strings: {^, a, aa, aab, aabb, aaaab, ab......}

So there is always one a for one b but extra a are possible. infect string can be consist of a only. Also notice ^ null is a member of language because in ^ NumberOf(a) = NumberOf(b) = 0

How to write a grammar that accepts the language formed by strings a^m bⁿ?

In the grammar, there should be rules such that if you add a b symbol you also add a a symbol.

and this can be done with something like:

   S --> aSb 

But this is incomplete because we need a rule to generate extra as:

   A --> aA | a

Combine two production rules into a single grammar CFG.

   S --> aSb | A
   A --> aA  | a

So you can generate any string that consist of a also a and b in (a^m bⁿ) pattern.

But in above grammar there is no way to generate ^ string.

So, change this grammar like this:

   S --> B   | ^
   B --> aBb | A
   A --> aA  | a

this grammar can generate {a^m bⁿ | m >= n} language.

Note: to generate ^ null string, I added an extra first step in grammar by adding S--> B | ^, So you can either add ^ or your string of symbol a and b. (now B plays role of S from previous grammar to generate equal numbers of a and b)

Edit: Thanks to @Andy Hayden
You can also write equivalent grammar for same language {a^m bⁿ | m >= n}:

   S --> aSb | A
   A --> aA | ^

notice: here A --> aA | ^ can generate zero or any number of a. And that should be preferable to my grammar because it generates a smaller parse tree for the same string.
(smaller in height preferable because of efficient parsing)

The following tips may be helpful to write Grammar for a formal language:

• You are to be clear about language that what it describes (meaning/pattern).
• You can remember solutions for some basic problems(the idea being that you can write new grammars).
• You can write rules for fundamental languages like I have written for RE in this example to write Right-Linear-Grammmar. The rules will help you to write Grammar for New Languages.
• One different approach is to first draw automata, then convert automata to Grammar. We have predefined techniques to write grammar from automata from any class of formal language.
• Like a Good Programmer who learns by reading the code of others, similarly one can learn to write grammars for formal languages.

_{Also the grammar you have written is wrong.}

Mazurka

two related pests two this (1) Why the need for terminals? Is my solution sufficient enough? ,(2) Why s--> ^ and A --> a ? in Context Free Grammars – Mazurka

You could have put the empty string at the end S --> aSb | A, A --> aA | ^, that way it's not a special case (and I think more intuitive). – Perni

Answer 2

you want to create a grammar for following language

    L= {an bm | m>=n }

that means number of 'b' should be greater or equal then number of 'a' or you can say that for each 'b' there could at most one 'a'. not other way around.

here is grammar for this language

      S-> aSb | Sb | b | ab

in this grammar for each 'a' there is one 'b'. but b can be generated without generating any 'a'.

you can also try these languages:

           L1= {an bm | m > n }
           L2= {an bm | m >= 2n }
           L3= {an bm | 2m >= n }
           L4= {an bm | m != n }

i am giving grammar for each language.

for L1

         S-> aSb | Sb | b

for L2

         S-> aSbb | Sb | abb

for L3

         S-> AASb | Sb | aab | ab | b

for L4

        S-> S1 | S2
        S1-> aS1b | S1b | b
        S2-> aS2b | aS2 | a

Firstrate

in first case we can't add L1 : bS also ?? S - > aSb | Sb | bS | b – Litha

@MohamedAdel Why add bS? Anand is right with L1. I guess L3 is wrong, because he hasn't defined A. – Mistreat

L3 should have a S -> aaSb production instead, yeah. – Jollification

Answer 3

Least variables: S -> a S b | a S | e

Folkmoot

Answer 4

with less variables :

S -> a S b | a S | a b | e

Navarra

may be you wanted to write small 'A' and 'B' ? presently your grammar doesn't drives terminals. – Mazurka

@GrijeshChauhan please give me a example, which terminal doesn't produce ??? but you are right about ("small A and B") I corrected them. – Navarra

No, now it is correct grammar, and yes because of less number of variables, your grammar is better than mine :) – Mazurka

Do you really need ab here? Wouldn't a e b cover that? – Zwieback