What language is generated by each of the BNF grammars below (assuming s is the start symbol):
<s> -> <x> | <y>
<x> -> 0 <x> 1 | <x1>
<x1> -> 0 <x1> | 0
<y> -> 0 <y> 1 1 | <y1>
<y1> -> <y1> 1 | 1
i understand what it does: 0^n 1^n
but i previously asked for help online (elsewhere) and someone gave me an answer:
For <x>: 0^n 1^m where n > m and m >= 0
For <y>: 0^n 1^m where m > 2n and m >=0
I can't quite follow it, where do the inequalities come from?
Why is n greater than m? Why is m greater than 2n?
I'm guessing the 2n is from the two 1s from y, but how does one figure out if n is greater or less than m? and vice versa? I'm completely oblivious.
Let's take x for example.
<x1> -> 0 <x1> | 0 <x1>: 0^n, n > 0
<x> -> 0 <x> 1 | <x1>
This means that x will be of the form:
<x>: 0^m 0^n 1^m, n >= 1, m >= 0
since if there will always be a x1 in the middle of 0^m 1^m. If we simplify we will have
<x>: 0^(m + n) 1^m, n >= 1, m >= 0
m + n > m since n is strictly positive.