Search code examples
bnf

What language is generated by each of the BNF grammars below

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.

Solution

  • 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.