0
votes

i have this question where I have to write a context free grammar for the following conditions using recursion method.

strings have equal numbers of x and y. For example your language will accept following strings xy, xyxy, xyxyxy, xxxyyy, xxyxyy, but will reject xyx, xxxyy, xxy, yyxxx, ... .

i come up with an answer S -> xSy| ySx |SS | e

But i am not sure if I did this right using recursion method.

1
Looks good to me, though it's been a few years.Kevin
This is correct grammar.Grijesh Chauhan

1 Answers

0
votes

S -> 0S1S | 1S0S | ^

String may start from 0 or 1 and whenever a 0 come , 1 should also be there and whenever a 1 come , a 0 should be there, so that 0's equal to 1's its not regular language