Tips for creating “Context Free Grammar”

问题:

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.

回答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.}

回答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

回答3:

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

回答4:

with less variables :

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