Constructing grammar based on given rules

Question

I have to construct a certain grammar for a given language where the language consists of strings of 0s and 1s that are the binary repr. of odd numbers greater that 6. I also have to create a parse tree for something like 10001 which is 17. How do I go about this problem?

Answer 1

To construct a grammar for a language consisting of strings of 0s and 1s that represent binary representations of odd numbers greater than 6, you can:

• identify the patterns: Odd numbers in binary always end with a 1. Numbers greater than 6 (in binary, greater than 110) must have at least 4 digits because 111 (7 in binary) is the smallest 3-digit odd number greater than 6.

• Define a context-free grammar (CFG) for this language. That grammar needs to make sure that:

  • the number is at least 4 digits long.
  • it ends with a 1 (to make sure it is odd).
  • it starts with at least 1001 to guarantee it is greater than 6.

You can set:

• S as the start symbol.
• B as a non-terminal that generates any binary digit (0 or 1).
• F as a non-terminal that generates a string ending in 1.

With the grammar:

S → 1F | 10F | 11F
F → 001 | 01 | 1F | 0F | BBF
B → 0 | 1

It starts by making sure the binary representation begins with 1 (so it is an actual binary number and not just a string of 0s), and it allows for generation of numbers that are at least 4 digits long and end with a 1.

S → 1F |   10F  | 11F
     |       |      |
     ↓       ↓      ↓
     F       F      F
    /|\     /|\    /|\
   001 01  1F 0F  BBF 1

---

Parse Tree for 10001 (17 in binary)

It fits the pattern defined by this grammar: it is a binary number greater than 6 and odd.

        S
        |
       10F
        |
       001  (Since 10001 ends in 001 after the initial 10)
        |
       1 (Terminal, ending the string with an odd number)

---

Actually, checking the Wikipedia definition of context-free grammar (CFG):

A context-free grammar G is a 4-tuple G = (V, Σ, R, S) where:

1. V is a finite set; each element v ∈ V is called a variable. Each variable represents a different type of phrase or clause in the sentence.
2. Σ is a finite set of terminals, disjoint from V, which make up the actual content of the sentence. The set of terminals is the alphabet of the language defined by the grammar G.
3. R is a finite relation in (V × (V ∪ Σ)*). The members of R are called productions of the grammar (symbolized by P).
4. S is the start variable, used to represent the whole sentence. It must be an element of V.

In your case:

• Variables (V): S (start), B (binary digits), E (end with 1)
• Terminals (Σ): 0, 1
• Productions (R):
  • S → 1B1 (starts and ends with 1, ensuring it is odd and greater than a certain minimum)
  • B → 0B | 1B | ε (generates binary sequences)
  • E → 1 (ensures the string ends with 1, making it odd)
• Start Variable (S): S

That way, I can use 0x51-dev/cfg in Go.
You can execute this example in the playground](https://go.dev/play/p/0FZ27_m9BZt)

It returns:

10001 is a valid representation of an odd number greater than 6.

package main

import (
    "fmt"
    "github.com/0x51-dev/cfg"
)

func main() {
    S := cfg.Variable("S")
    B := cfg.Variable("B")
    zero := cfg.Terminal("0")
    one := cfg.Terminal("1")

    g, err := cfg.New(
        []cfg.Variable{S, B}, // Variables
        []cfg.Terminal{zero, one}, // Terminals
        []cfg.Production{ // Productions
            cfg.NewProduction(S, []cfg.Beta{one, B, one}),
            cfg.NewProduction(B, []cfg.Beta{zero, B}),
            cfg.NewProduction(B, []cfg.Beta{one, B}),
            cfg.NewProduction(B, []cfg.Beta{cfg.Epsilon}),
        },
        S, // Start Variable
    )
    if err != nil {
        fmt.Println("Error creating CFG:", err)
        return
    }

    binaryString := "10001" // Binary representation of 17
    _, ok := g.Evaluate(binaryString)
    if ok {
        fmt.Println(binaryString, "is a valid representation of an odd number greater than 6.")
    } else {
        fmt.Println(binaryString, "is NOT a valid representation of an odd number greater than 6.")
    }
}

Answer 2

Had to clutch up and solve it my self.