Question: L = { w in { 0 , 1 } * : w w w : where | w | = | w | or

L ={w in {0,1}*: www: where |w|=|w| or |w|=|w|}
Let's say, we have the following 4 CFGs labeled as (A) to (D).
CFG A:
S -> RQ | P
P ->0P1|1P0|\epsi
Q ->0Q |1Q |\epsi
R ->0R0|1R1|0R1|1R0| Q
CFG B:
S -> PR | Q
P ->0P0|1P1|\epsi
Q ->0Q |1Q |\epsi
R ->0R0|1R1|0R1|1R0| Q
CFG C:
S -> PQ | R
P ->0P0|1P1|0P1|1P0|\epsi
Q ->0Q |1Q |\epsi
R ->0R0|1R1|0R1|1R0| Q
CFG D:
S -> PQ | R
P ->0P0|1P1|0P1|1P0|\epsi
Q ->0Q |1Q
R ->0R0|1R1|0R1|1R0| P
What will be the correct CFG for the language L?
Note, for a language L, the CFG will be correct if and only if it can parse all the strings, w in L, and doesnt parse any string, w L.
2 points
A and C
B and C
C and D
A, B and C
A, B, C and D

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Programming Questions!