Writing Context Free Grammar: Sabrina, Year 10

[sabrina123456]

I am sabrina, year 10 at school. I have question of how to write Context free grammar >

The set of all strings beginning with a string of occurrences of the first letter specified above, and ending with a string of occurrences
of the second letter specified above. In the middle is a string of the character
c. If the number of occurrence of the first letter is n and the number of
occurrence of the second letter is m, then the number of occurrences of c is x.n
+ y.m + 1.
For example, the language is a^n c^x.n + y.m + 1b^m, with x=2, y=3,
and includes accccccbb and aacccccb.

And this is what I actually wrote below to write the context free grammar:

S -> ABC
A - > Aa
A - > a
B - > Bb
A - > b
C - > c

is this correct? Please I need help and i am trying to learn my best. Thank you for your help.

Regards

Sabrina

 

[Filip Larsen]

For example, the language is a^n c^x.n + y.m + 1b^m, with x=2, y=3,
and includes accccccbb and aacccccb.

I'm a bit confused, because if the language is aⁿc^2n+3m+1c^m, then for n = 1 and m = 2 (for the first example above) we should get 2n+3m+1 = 2+6+1 = 9 c's but in the example there are only 6. Likewise for the second there should be 8 c's but there are 5 in the example. Perhaps you made a typo somewhere?

And this is what I actually wrote below to write the context free grammar:

S -> ABC
A - > Aa
A - > a
B - > Bb
A - > b
C - > c

is this correct?

No. It has (what appears as) some "spelling mistakes", but even if you fix this it will not generate the specified language. For the grammar to do that you should check that all string generated by the grammar are in the language and, visa versa, that all strings allowed by the language can be generated by the grammar.

You should try make a grammar that "ties" the generation of each a with the generation of x number of c's, and each generation of b with the generation of y number of c's, that is, you need some rules that generate the left, middle and the right part of the strings, where for instance the left part could be
L -> aLc^x
L -> e
where e means empty. You then need to figure out what the middle and right part should be (hint: the middle part is responsible for generating the c's that is not generated by neither the left nor right part).

 

[sabrina123456]

I am very depressed really :(. I understood what needs to be done, but I am afraid I do not how to write Context-Free Grammar properly, i tried my best to spend hours working this, but I really wish you could help.

Much appreciated for your support.


Regards

Sabrina

 

[Filip Larsen]

No need to be depressed about it. I assume you are doing this for your own fun (as the subject is not something people at your age normally would be required to understand) and if so you should keep it fun.

If you still want to give it a go, I (or someone else here) could give it a try explaining the solution which is not that difficult, but then I would like to know first for what purpose you need to know about context free grammars. Normally context free grammars are used in connection with designing computer languages and programs for handling these, but maybe you have another reason for wanting to know about it?

 

[DeeNos]

, Year 10

Hi Sabrina, Year 10,

Your attempt at writing a context-free grammar is a great start! However, there are a few things that can be improved upon.

First, the production rules should be labeled with non-terminals (i.e. capital letters) and terminals (i.e. lowercase letters or symbols). So, your grammar should look like this:

S -> A B C
A -> A a
A -> a
B -> B b
B -> b
C -> c

This means that the start symbol is S and the non-terminals are A, B, and C. The terminals are a, b, and c.

Next, the production rules should be written in the form of "non-terminal -> a combination of terminals and non-terminals". So, for example, the rule A -> Aa should be written as A -> aA. This ensures that the grammar is in the correct form.

Finally, the production rules should be written in a way that generates the language described in the content. Based on the content provided, the grammar should generate strings like "a^n c^x.n + y.m + 1b^m", where n and m are the number of occurrences of the first and second letter respectively, and x and y are constants. This means that the grammar should look like this:

S -> a^n C b^m
C -> c C | c

where n, m, x, and y are constants that can be adjusted to generate different strings in the language.

I hope this helps and good luck with your learning journey!

Best regards,

Scientist