4. Context Free Grammar
A context-free grammar (CFG) is a set of recursive rewriting rules (or productions) used to generate patterns of strings.
A CFG consists of the following components:
- a set of terminal symbols, which are the characters of the alphabet that appear in the strings generated by the grammar.
- a set of non-terminal symbols, which are placeholders for patterns of terminal symbols that can be generated by the non-terminal symbols.
- a set of productions, which are rules for replacing (or rewriting) non-terminal symbols (on the left side of the production) in a string with other non-terminal or terminal symbols (on the right side of the production).
- a seed, which is a special non-terminal symbol that appears in the initial string generated by the grammar.
To generate a string of terminal symbols from a CFG, we:
- Begin with a string consisting of the start symbol;
- Apply one of the productions with the start symbol on the left hand side, replacing the start symbol with the right hand side of the production;
- Repeat the process of selecting non-terminal symbols in the string, and replacing them with the right hand side of some corresponding production, until all non-terminals have been replaced by terminal symbols.
For example, this specification:
A = BD
B = bB | b | Bb
D = dD
D = d
with A as the seed represents the set of words that have one or more b's followed by one or more d's (bd, bbd, bddd, bbbddd, etc.).
Above production grammar contains string “bbd”. So your task is to find out the given string can be formed by given grammar or not. If that string can formed by the given grammar then return true otherwise false.
Instructions to use Open PBT Client:
- Specify the work directory path in the 'Work Directory Path' field. The path should correspond to your solution work directory.
- Download the Support files by clicking the Get Support Files
.
- You will find the problem directories containing:
- problem.h file
- problem.c file
in your work directory.
- Write your solution in .c file
Step 1:
In your Solution File:
- Add method int checkString(char** production, char seed, char* str)
Step 2:
Pass the following parameter to the method checkString()
- production is a character pointer array represents the available productions for the CFG as mentioned in the problem description.
- seed
is a character,which is a special non-terminal symbol that appears in the initial string generated by the grammar.
- str is a String which can be created by the given productions.
Step 3:
Write the appropriate code as mentioned in the problem description by following the below given Constraints.
- The first input should be the String Array which specify the production to the given grammer in the format given below:
{"S=aSa" , "S = bSb" , "S=aa" , "S =bb"}
- The second input is the seed character,which is a special non-terminal symbol that appears in the initial string generated by the grammar.
- The third input is the string itself, which you have to determine whether it is generated by the above given production
- You need to figure out whether the string (the third input) can be generated by the given production (the first input) by using the seed (second input) as a initial non-terminal symbol.
- Your method should return true if it can be generated else return false
- If the given production string is null then return false.
The prototype of the function is:
int checkString(char** production, char seed, char* str)
Where production is the string array.
seed is the character.
str is the string .
Constraint:
- If the given production string is null then return false.
Example 1
Input:
Production String:
|
{"S=aSa" , "S = bSb" , "S=aa" , "S =bb"}
|
seed character:
|
S
|
Desired string:
|
"abaaba"
|
Output:
true
Explanation:The string "abaaba" can formed by using production
S=aSa---->S=a(bSb)a------->S=ab(aa)ba---------->S=abaaba
Example 2
Input:
Production String:
|
{"A = BD", "B = bB | b | Bb", "D = dD", "D = d"}
|
seed character:
|
A
|
Desired string:
|
"bbb"
|
Output:
false
For C++ solutions
Header File
|
:
|
ContextFreeGrammar.h
|
Class Name
|
:
|
ContextFreeGrammar
|
Function Name
|
:
|
int checkString(char** production, char seed, char* str);
|
FileName
|
:
|
ContextFreeGrammar.cpp
|
General Instructions
*
|
The file / class names, functions, method signatures, header files to be used are mentioned in the problem statement. Do not use your own names or change the method signatures and fields. You can add any number of additional methods.
|
*
|
Do not forget to mention the file extension, either .c or .cpp as the case maybe.
|
*
|
For C solutions, change the value of "C_OR_CPP" macro in header file to 1 and for C++ solutions change the value to 2.
|
*
|
Incase of iostream.h specify as iostream only.
|
|
Rajesh
7306947200
pedana
krishna dt
|
 |
JOKES CORNER:
Some Good "Poor Jokes"...
Here are some really bad pj's...Read on if u like some...
Lion Roaring...
what happens when the lion roars???
...
TOM & JERRY Begins......
Hights of Optimism:r
Soldier: "Sir we are surrounded by enemies on all sides!!!"
Sardar Major" Excellent!!! we can attack in any direction"
Flirt like this
What is the height of Flirting?
Its When your love letter starts with "TO WHOMSOEVER IT MAY CONCERN"
|
 |
..
BRILLIANT WAYS GIRLS TURN GUYS DOWN!!
HE: I'm a photographer I've been looking for a face like yours!
SHE: I'm a plastic surgeon. I've been looking for a face like yours!!!
HE: May I have the pleasure of this dance?
SHE: No, I'd like to have some pleasure too!!!
the sardar...
Q: Why did the Sardar take a pair binoculars with him to a funeral?
A: It was a distant relative's funeral.
gabbbar...
Gabber: Kitne Aadmi they.
Sambha: Sardar Do,
Gabber: Mujhe ginti nahi aati. Do kitne hotey hain?
Sambha: Sardar Do Ek ke baad aata hai.
Gabber : Aur Do ke pehle?
Sambha: Do ke pehle Ek aata hai.
Gabber: To beech mein kaun aata hai?
Sambha: Beech mein koi nahi aata.
Gabber: To fir Dono ek saath kyon nahi atey?
Sambha: Do Ek ke baad hi aa sakta hai, kyonki Do ek se bada hai.
Gabber: Do ek se bada hai? Kitna bada hai?
Sambha Do ek se Ek bada hai?
Gabber: Agar Do ek se ek bada hai to ek ek se kitna bada hai?
Sambha: Sardar, Maine tumhara namak khaya hai, mujhe goli mar do
ek ladki...
A Lady is standing up on top of the hill and she is going to push her Father down from the hill top.....
SO what is the name of this lady ???
... Well her Name is PUSH-PA!!!!!!!!!!
HE: How did you get to be so beautiful?
SHE: I must have been given your share!!!
HE: Will you come out with me this Saturday?
SHE: Sorry! I'm having a headache this weekend!!!
HE: Go on, don't be shy. Ask me out!
SHE: Okay, get out!!!
HE: I think I could make you very happy
SHE: Why? Are you leaving?
HE: What would you say if I asked u to marry me?
SHE: Nothing. I can't talk and laugh at the same time!!!
HE: Can I have your name?
SHE: Why, don't you already have one?
HE: Shall we go and see a film?
SHE: I've already seen it!!!
HE: Do you think it was fate that brought us together?
SHE: Nah, it was plain bad luck!!!
|
|