Why s--> ^ and A --> a ? in Context Free Grammars

Question

I've been reading: "Tips for creating Context free grammar" post for learning purposes and I nearly understand the concept, but I don't quite understand the following.

If we have:

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

I understand this:

S --> B
B --> aBb
A  --> aA

But what I don't understand is the concept of adding to the end of these particular values, such as:

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

Why do we add ^ (null), A, and a to the end of these lines? What do they do and why do we need them?

All help is greatly appreciated.

Catch

thanks for the feedback, a small explanation added in my answer too.. – Adaiha

Answer 1

You need them to be able to construct the strings that are in the language L.

B --> aBb | A means that if you have a nonterminal B it can be replaced by either aBb or A. (Capital letters represent nonterminals and the lower case letters represent terminals).

Let's take a look at the grammar:

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

Why do we have a | ^? You need it to be able to generate the empty string. The empty string is clearly part of the language L since it contain an equal amount of as and bs.

Why do we have | A? To be able to use the rule for A. Now you can replace B with A so you can insert either aA or a. You need this rule to be able to generate strings that have more as than bs.

Why do we have | a? To be able to replace A with a without adding a new nonterminal that need to be replaced.

When I look at this grammar I would say that you need to change A --> aA | a to A --> aA | a | ^ to be able to generate strings with an equal amount of as and bs. (So you can replace A with the empty string (or null) instead of having to add an extra a)

Let's say you want to generate the string aaabb:

S       //You start with S
B       //Rule: S --> B
aBb     //Rule: B --> aBb
aaBbb   //Rule: B --> aBb
aaAbb   //Rule: B --> A
aaabb   //Rule: A --> a

Impudent

Brilliant, thanks! Can you explain what this symbol means: d.pr/i/3YG1 - thanks again. – Catch

@Xiy That sign is the "not equal" sign. See this – Impudent

@Impudent also read this I tried to cove your explanation. also you may like you suggest something :) – Adaiha

Answer 2

The need for the extra ^,A and a is to complete the grammar set.

Thus A --> aA takes care of [aa, aaa, aaaa, ...]

A --> aA | a takes care of [a, aa, aaa, aaaa, ...]

B --> aBb takes care of [ab, aabb, aaabbb, ...]

So, B --> aBb | A should take care of [a, ab, aa, aab, aaa, aaab, aabb, ...]

The only one missing is ^

So now complete the grammar with S --> B | ^ [^, a, aa, ab, aaa, aab, aaaa, aaab, aabb, ...]

As you can see, it is not possible to generate the 2nd half from the first half, but it is also a subset of the grammar. So, in order to complete the grammar, that 2nd half is crucial as well. Look at the wikipedia article for clearer examples.

http://en.wikipedia.org/wiki/Context-free_grammar

Timepleaser