Questions about Backus Naur Form

Question

I’m having second thoughts about the BNF exercises.

1. Write a BNF to generate sequences of binary digits in pairs for example: 0 0 11 0 0, 11 00 1 1 , 1 1 1 0 0 1 1
2. Write a BNF to generate sequences that have a digit in a row exactly a capital letter , for example 1 A , 2 B , 4 A , 3 C , 1 A , 2 B

Answer 1

BNF is nothing more than a glorified notation for productions of formal grammars, often used for context-free grammars. She has her quirks, which are:

1. non-terminal are denoted by <angle braces>, whereas <a> is equivalent to non-terminal a of the grammar in question (the Angle braces are mere syntactic indicators)
2. terminals are denoted by "aspas"; they can be a string of terminals, so "banana" consists of a terminal of length 6
3. there is the empty word, which some authors of formal grammars in the more mathematical part of the thing denote by ε or λ, here devoured by ""
4. the production is indicated by ::=, where the left side generates the right
5. if the non-terminal has alternative productions, they are indicated by a vertical bar | (I saw nothing prohibiting repeating the left side of the production, so this is more by notation concision)
6. any possibility of concatenating terminal/non-terminal symbols can be done using spaces, for example <pré-nome> " de " <sobrenome>
7. one production per line

That being said, as an exercise, I will leave to the reader the responsibility of transforming the informal notation of grammar that I will use here for formal BNF.

For the first example, we can use the following productions:

S -> PAR S
S -> PAR
PAR -> "00"
PAR -> "11"

I don’t know if the empty word is accepted in the language, if it is, just change the production S -> PAR for S -> "".

Note here how the productions of S always generate concatenations of PAR, and PAR can only generate "00" or "11".

The second, in turn, is simpler:

S -> DÍGITO MAIÚSCULA

I’m not writing the 10 productions for DÍGITO nor the 26 to MAIÚSCULA for practicality, and that you, reader, understood the point of the answer.

---

By the way, although I have written using context-free productions, both languages are regular. It takes a little more work to write using only the regular productions on the right (the terminal being on the left and the nonterminal on the right), but they are trivially transformed into regular grammars.