How to write grammar for a formal language?
Before reading my answer, you should first read: Tips for creating contextual free grammars .
Grammar for {a n b m | n, m = 0,1,2, ..., n <= 2m}
What is your language L = {a n b m | n, m = 0,1,2, ..., n <= 2m} description?
Description of the language : The language L consists of the set of all lines in which the characters a followed by the characters b , where the number of characters b greater than or equal to half > the number a .
To understand more clearly:
In the pattern a n b m, the first characters of a then come to character b . the total number a is n , and the number b is m . The inequality equation speaks of the relationship between n and m . To understand the equation:
given: n <= 2m => n/2 <= m means `m` should be = or > then n/2 => numberOf(b) >= numberOf(a)/2 ...eq-1
Thus, the inequality n and m says:
numberOf ( b ) must be greater than or equal to half the number OFF ( a )
Some example lines in L:
b numberOf(a)=0 and numberOf(b)=1 this satisfy eq-1 bb numberOf(a)=0 and numberOf(b)=2 this satisfy eq-1
Thus, in a language string, any number b possible without a . (any line from b), because any number is greater than zero (0/2 = 0).
Other examples:
mn -------------- ab numberOf(a)=1 and numberOf(b)=1 > 1/2 abb numberOf(a)=1 and numberOf(b)=2 > 1/2 abbb numberOf(a)=1 and numberOf(b)=3 > 1/2 aabb numberOf(a)=2 and numberOf(b)=2 > 2/2 = 1 aaabb numberOf(a)=3 and numberOf(b)=2 > 3/2 = 1.5 aaaabb numberOf(a)=4 and numberOf(b)=2 = 4/2 = 2
Note:
all of the above lines are possible because the number b is equal (=) to half the number a or more (>).
and it is interesting to note that the final value of a can also be greater than the number b , but not too much. While the number b can be greater than the number a for any number of times.
Two other important cases:
only a as a string is not possible.
note: the string null ^ also allowed, since in ^ , numberOf(a) = numberOf(b) = 0 , which satisfy the equation.
It’s immediately obvious that the grammar is hard-written, but not really ...
In accordance with the description of the language, we need the following types of rules:
rule 1 : generate ^ null string.
N --> ^
rule 2 . To create any number b
B --> bB | b
Rule 3 : to generate a :
(1) Remember that you cannot generate too much a without generating b .
(2) Because b greater = = half a ; you need to generate one b for each alternative a
(3) Only a as a string is not possible, so for the first (odd) alternative, you need to add b with a
(4) If, for an alternative, you can opt out of adding b (but not necessarily)
So you have a common grammar:
S --> ^ | A | B B --> bB | b A --> aCB | aAB | ^ C --> aA | ^
here S runs the variable.
In the grammar rules above, you may have confusion in A --> aCB | aAB | ^ A --> aCB | aAB | ^ A --> aCB | aAB | ^ , so below is my explanation:
A --> aCB | aAB | ^ ^_____^ for second alternative a C --> aA <== to discard `b` and aAB to keep b
let's generate some lines in the language using these grammar rules, I write the leftmost output to avoid explanation.
ab S --> A --> aCB --> aB --> ab abb S --> A --> aCB --> aB --> abB --> abb abbb S --> A --> aCB --> aB --> abB --> abB --> abbB --> abbb aabb S --> A --> aAB --> aaABB --> aaBB --> aabB --> aabb aaabb S --> A --> aCB --> aaAB --> aaaABB --> aaaBB --> aaabB --> aaabb aaaabb S --> A --> aCB --> aaAB --> aaaCBB --> aaaaABB --> aaaaBB --> aaaabB --> aaaabb
Another line for non-member:
in the language a 5 b 2 = aaaaabb maybe not . because 2> = 5/2 = 2.5 ==> 2> = 2.5 the inequality fails. Therefore, we cannot generate this string using grammar. I am trying to show below:
In our grammar, to generate additional a we must use the variable C.
S --> A --> aCB --> aaAB --> aa aCB B --> aaa aA BB --> aaaa aCB BB --- ^ here with firth `a` I have to put a `b` too
So far my answer has been made, but I think you can change the rules of a , for example:
A --> aCB | A | ^
Give it a try!
EDIT:
as @ us2012 commented: It seems to me that then S -> ^ | ab | aaSb | Sb S -> ^ | ab | aaSb | Sb S -> ^ | ab | aaSb | Sb will be a simpler description. I believe that this question will be useful for both the OP and others.
Language OP:
L = {a n b m | n, m = 0,1,2, ..., n <= 2m}.
@ us2012 Grammar:
S -> ^ | ab | aaSb | Sb
@ us2012 question:
Is this grammar also an L language?
Answer Yes!
The inequality in language between the number a = n and the number b = m is n =< 2m
We can also understand:
n =< 2m that is numberOf(a) = < twice of numberOf(b)
And in the grammar, when we add one or two a , we also add one b . Thus, in the end, the number a cannot be more than two times from the number b .
Grammar also has rules for generating. any number of lines b and null ^ .
Thus, the simplified grammar provided by @ us2012 is CORRECT and also expresses the language L. accurately.
Note: The first solution came from derivation, as I wrote in a related answer, I started with a description of the language, then tried to write some basic rules, and gradually I could write a complete grammar.
While @ us2012's answer came by ability, you can gain the ability to write grammar by reading another solution and writing your own for the same ... how do you learn programming.