Question

For this problem, Give a BNF grammar for each of the descriptions below. show that you can get a number of positive examples of the language in the constructed grammar and also show that you are not able to get a set of negative examples in the grammar. Create a parse tree for the grammar after.

1). The set of all string consisting of an uppercase letter followed by zero or more additional characters, each of which is either an uppercase letter or one of the digits 0 through 9.

2). The set of all strings consisting of an open bracket (the symbol ‘[‘) followed by a list of one or more digits separated by commas, followed by a closing bracket (the symbol ‘]’)

Answer 1

Solution

In BNF, productions have the form:

Left side → definition  

Where leftside ∈ (Vn∪ Vt)+ and definition ∈ (Vn∪ Vt)*. In BNF, the leftside contains one non-terminal, where Vn is a nonterminal and Vt is a terminal.

Part 1

The set of all string consisting of an uppercase letter followed by zero or more additional characters, each of which is either an uppercase letter or one of the digits 0 through 9.

NT1 -> NT2 .NT3

NT3 -> NT2 NT3 | NT4 NT3 | ϵ

NT2 -> A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z

NT4 -> 0|1|2|3|4|5|6|7|8|9

Here, NT1, NT2, NT3 and NT4 are the non terminals.

0,1,2,3,4,5,6,7,8,9, A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z are the terminals.

Part 2

The set of all strings consisting of an open bracket (the symbol ‘[‘) followed by a list of one or more digits separated by commas, followed by a closing bracket (the symbol ‘]’)

NT1 -> [ NT2 ]

NT2 ->NT3,NT2 | NT3

NT3 -> 0|1|2|3|4|5|6|7|8|9

Here NT1, NT2, NT3 are the non terminals and 0,1,2,3,4,5,6,7,8,9 and ',' are the terminals